import struct,bisect
def parse(b):
    assert b[:4]==b'MThd'
    length,fmt,ntracks,ppq=struct.unpack('>IHHH',b[4:14]);assert not ppq&0x8000
    p=8+length;events=[];tempos=[(0,500000)]
    for tr in range(ntracks):
        assert b[p:p+4]==b'MTrk';end=p+8+int.from_bytes(b[p+4:p+8],'big');p+=8;tick=0;running=0
        def vlq():
            nonlocal p
            n=0
            while True:
                v=b[p];p+=1;n=(n<<7)|(v&127)
                if v<128:return n
        while p<end:
            tick+=vlq();st=b[p]
            if st>=128:p+=1;running=st
            else:st=running
            if st==255:
                typ=b[p];p+=1;n=vlq();data=b[p:p+n];p+=n
                if typ==81:tempos.append((tick,int.from_bytes(data,'big')))
                continue
            if st in [240,247]:p+=vlq();continue
            a=b[p];p+=1;v=0
            if st&240 not in [192,208]:v=b[p];p+=1
            events.append((tick,tr,st,a,v))
        assert p==end
    tempo=dict(tempos);tt=sorted(tempo);secs=[0.0]
    for a,c in zip(tt,tt[1:]):secs.append(secs[-1]+(c-a)*tempo[a]/ppq/1e6)
    def seconds(t):
        k=bisect.bisect_right(tt,t)-1;return secs[k]+(t-tt[k])*tempo[tt[k]]/ppq/1e6
    held={};notes=[];cc=[]
    for tick,tr,st,pitch,vel in sorted(events,key=lambda e:(e[0],e[1])):
        key=(tr,st&15,pitch);t=seconds(tick)
        if st&240==144 and vel:held.setdefault(key,[]).append((t,vel,tick))
        elif st&240==128 or (st&240==144 and not vel):
            if held.get(key):
                start,v,nt=held[key].pop(0);notes.append({'pitch':pitch,'start':start,'duration':t-start,'velocity':v,'track':tr,'channel':st&15})
        elif st&240==176:cc.append({'time':t,'controller':pitch,'value':vel,'track':tr,'channel':st&15})
    return {'format':fmt,'tracks':ntracks,'ppq':ppq,'tempos':[(x,tempo[x]) for x in tt],'notes':sorted(notes,key=lambda n:(n['start'],n['pitch'])),'controls':cc,'danglingNotes':sum(map(len,held.values()))}
def max_polyphony(notes):
    n=mx=0
    for t,x in sorted([(n['start'],1) for n in notes]+[(n['start']+n['duration'],-1) for n in notes]):n+=x;mx=max(mx,n)
    return mx