Submission #67790344

---

Source Code Expand

import sys
input = sys.stdin.readline

from heapq import heappop,heappush


T=int(input())
for tests in range(T):
    n=int(input())
    A=list(map(int,input().split()))
    K=[1]*n

    ANS=0
    H=[]

    for i in range(n):
        H.append((A[i],i))

    H.sort()

    LEFT=[i-1 for i in range(n)]
    RIGHT=[i+1 for i in range(n)]

    USE=[0]*n

    for tt in range(n-1):
        #print(A,USE,H,ANS)
        while H:
            x,ind=heappop(H)

            if USE[ind]==1:
                continue
            if A[ind]!=x:
                continue
            break

        p=1<<60
        m=1<<60

        if RIGHT[ind]<len(A):
            p=A[RIGHT[ind]]

        if LEFT[ind]>=0:
            m=A[LEFT[ind]]

        #print(ind)

        if p>m:
            x=A[ind]
            ko=K[ind]


            while x<m:
                if ko==1:
                    ANS+=(m-x)
                    break
                if ko%2==0:
                    ko//=2
                    x+=1
                else:
                    ko=(ko+1)//2
                    ANS+=1
                    x+=1


            #A[LEFT[ind]]+=1
            USE[ind]=1
            K[LEFT[ind]]+=ko

            if 0<=LEFT[ind]<n:
                RIGHT[LEFT[ind]]=RIGHT[ind]

            if 0<=RIGHT[ind]<n:
                LEFT[RIGHT[ind]]=LEFT[ind]


        else:
            x=A[ind]
            ko=K[ind]


            while x<p:
                if ko==1:
                    ANS+=(p-x)
                    break
                if ko%2==0:
                    ko//=2
                    x+=1
                else:
                    ko=(ko+1)//2
                    ANS+=1
                    x+=1


            #A[RIGHT[ind]]+=1
            USE[ind]=1
            K[RIGHT[ind]]+=ko

            if 0<=LEFT[ind]<n:
                RIGHT[LEFT[ind]]=RIGHT[ind]

            if 0<=RIGHT[ind]<n:
                LEFT[RIGHT[ind]]=LEFT[ind]

    #print(ANS,A,USE,K)

    for i in range(n):
        if USE[i]==0:
            score=K[i]

    while score>1:
        if score%2==0:
            score//=2
        else:
            ANS+=1
            score=(score+1)//2

    print(ANS)
        

    
            
        

Submission Info

Judge Result