Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import random
    from math import log,ceil

    N=int(input())

    A=list(map(int,input().split()))
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=10**25
    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    #セグメント木
    #####segfunc######
    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)

    def init():
        #set_val
        for i in range(n):
            seg[i+num-1]=i
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

    

    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res

    #####単位元######
    ide_ele = N

    #num:n以上の最小の2のべき乗
    n=N
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num

    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    init()

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        S+=ope[i]
        B[i]+=ope[i]
    #print(time.time()-start)
    init()
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Fixed submission:
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = ide_ele
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = i
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import random
    from math import log,ceil

    N=int(input())
    n=N

    A=list(map(int,input().split()))
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=10**25
    ope=[0 for i in range(N+1)]
    ope[N]=10**20

    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)
    #####ide_ele#####
    ide_ele = N
    #################


    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    rmq=SegTree(segfunc,ide_ele)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        S+=ope[i]
        B[i]+=ope[i]
    #print(time.time()-start)
    rmq=SegTree(segfunc,ide_ele)
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import random,time
    from math import log,ceil

    N=int(input())

    A=list(map(int,input().split()))
    start=time.time()
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=float("inf")
    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    #セグメント木
    #####segfunc######
    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)

    def init():
        #set_val
        for i in range(n):
            seg[i+num-1]=i
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res

    #####単位元######
    ide_ele = N

    #num:n以上の最小の2のべき乗
    n=N
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num

    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    init()

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        S+=ope[i]
        B[i]+=ope[i]
    #print(time.time()-start)
    init()
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Fixed submission:
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = ide_ele
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = i
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import random
    from math import log,ceil

    N=int(input())
    n=N

    A=list(map(int,input().split()))
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=10**25
    ope=[0 for i in range(N+1)]
    ope[N]=10**20

    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)
    #####ide_ele#####
    ide_ele = N
    #################


    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    rmq=SegTree(segfunc,ide_ele)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        S+=ope[i]
        B[i]+=ope[i]
    #print(time.time()-start)
    rmq=SegTree(segfunc,ide_ele)
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import random,time
    from math import log,ceil

    N=int(input())

    A=list(map(int,input().split()))
    start=time.time()
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=float("inf")
    ope=[0]*N
    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    K=N.bit_length()
    table=[[-1 for i in range(K)] for i in range(N)]

    def init():
        for i in range(N):
            table[i][0]=i

        for j in range(1,K):
            for i in range(0,N-2**j+1):
                f=table[i][j-1]
                s=table[i+2**(j-1)][j-1]
                if ope[f]<ope[s]:
                    table[i][j]=f
                elif ope[f]>ope[s]:
                    table[i][j]=s
                else:
                    table[i][j]=min(s,f)

    def query(s,t):
        t-=1
        b=t-s+1
        m=b.bit_length()-1
        a,b=table[s][m],table[t-2**m+1][m]
        if ope[a]>ope[b]:
            return b
        elif ope[a]<ope[b]:
            return a
        else:
            return min(a,b)

    init()

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]
    n=N
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0]*N
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        B[i]+=ope[i]
    S=sum(ope[i] for i in range(N))
    #print(time.time()-start)
    init()
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)
    for i in range(1,N):
        while i!=zero[-1]:
            k=query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()


Fixed submission:
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = ide_ele
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = i
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import random
    from math import log,ceil

    N=int(input())
    n=N

    A=list(map(int,input().split()))
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=10**25
    ope=[0 for i in range(N+1)]
    ope[N]=10**20

    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)
    #####ide_ele#####
    ide_ele = N
    #################


    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    rmq=SegTree(segfunc,ide_ele)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        S+=ope[i]
        B[i]+=ope[i]
    #print(time.time()-start)
    rmq=SegTree(segfunc,ide_ele)
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import random,time
    from math import log,ceil

    N=int(input())

    A=list(map(int,input().split()))
    start=time.time()
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=float("inf")
    Init=[i for i in range(N)]
    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    #セグメント木
    #####segfunc######
    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)

    def init(init_val):
        #set_val
        for i in range(n):
            seg[i+num-1]=init_val[i]
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res

    #####単位元######
    ide_ele = N

    #num:n以上の最小の2のべき乗
    n=N
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num

    for i in range(1,N):
        c=max(0,ceil(A[i-1]-A[i]))
        ope[i]+=c
        A[i]+=c

    init(Init)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        c=max(0,ceil(B[i-1]-B[i]))
        ope[i]=c
        S+=c
        B[i]+=c
    #print(time.time()-start)
    init(Init)
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Fixed submission:
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = ide_ele
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = i
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import random
    from math import log,ceil

    N=int(input())
    n=N

    A=list(map(int,input().split()))
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=10**25
    ope=[0 for i in range(N+1)]
    ope[N]=10**20

    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)
    #####ide_ele#####
    ide_ele = N
    #################


    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    rmq=SegTree(segfunc,ide_ele)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        S+=ope[i]
        B[i]+=ope[i]
    #print(time.time()-start)
    rmq=SegTree(segfunc,ide_ele)
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import random,time
    from math import log,ceil

    N=int(input())

    A=list(map(int,input().split()))
    start=time.time()
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=float("inf")
    Init=[i for i in range(N)]
    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    #セグメント木
    #####segfunc######
    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)

    def init(init_val):
        #set_val
        for i in range(n):
            seg[i+num-1]=init_val[i]
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res

    #####単位元######
    ide_ele = N

    #num:n以上の最小の2のべき乗
    n=N
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num

    for i in range(1,N):
        c=max(0,ceil(A[i-1]-A[i]))
        ope[i]+=c
        A[i]+=c

    init(Init)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        c=max(0,ceil(B[i-1]-B[i]))
        ope[i]+=c
        S+=c
        B[i]+=c
    #print(time.time()-start)
    init(Init)
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    zero_append=zero.append
    for i in range(1,N):
        while i!=zero[-1]:
            k=query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero_append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Fixed submission:
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = ide_ele
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = i
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import random
    from math import log,ceil

    N=int(input())
    n=N

    A=list(map(int,input().split()))
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=10**25
    ope=[0 for i in range(N+1)]
    ope[N]=10**20

    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)
    #####ide_ele#####
    ide_ele = N
    #################


    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    rmq=SegTree(segfunc,ide_ele)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        S+=ope[i]
        B[i]+=ope[i]
    #print(time.time()-start)
    rmq=SegTree(segfunc,ide_ele)
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import random,time
from math import log,ceil

N=int(input())

A=list(map(int,input().split()))
start=time.time()
A=[log(A[i],4) for i in range(N)]
B=[A[-i-1] for i in range(N)]
memo=[0]*(N-1)
ans=float("inf")
Init=[i for i in range(N)]
ope=[0 for i in range(N+1)]
ope[N]=10**20
#セグメント木
#####segfunc######
def segfunc(x,y):
    if ope[x]>ope[y]:
        return y
    elif ope[y]>ope[x]:
        return x
    else:
        return min(x,y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = N

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

for i in range(1,N):
    c=max(0,ceil(A[i-1]-A[i]))
    ope[i]+=c
    A[i]+=c

init(Init)

S=sum(ope[i] for i in range(N))
ans=min(ans,2*S)
zero=[N]

#A1 ... AnのBIT(1-indexed)
BIT = [0]*(n+1)
#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

for i in range(1,N):
    while i!=zero[-1]:
        k=query(i,zero[-1])
        val=ope[k]+BIT_query(k+1)
        S-=val*(zero[-1]-i)
        BIT_update(i+1,-val)
        BIT_update(zero[-1]+1,val)
        zero.append(k)
    zero.pop()
    memo[i-1]+=2*S

ope=[0 for i in range(N+1)]
ope[N]=10**20
S=0
for i in range(1,N):
    c=max(0,ceil(B[i-1]-B[i]))
    ope[i]+=c
    S+=c
    B[i]+=c
#print(time.time()-start)
init(Init)
#print(time.time()-start)

ans=min(ans,2*S+N)
zero=[N]
BIT=[0]*(n+1)

zero_append=zero.append
for i in range(1,N):
    while i!=zero[-1]:
        k=query(i,zero[-1])
        val=ope[k]+BIT_query(k+1)
        S-=val*(zero[-1]-i)
        BIT_update(i+1,-val)
        BIT_update(zero[-1]+1,val)
        zero_append(k)
    zero.pop()
    memo[N-1-i]+=2*S+(N-i)
#print(time.time()-start)
test=min(memo)
print(min(test,ans))

Fixed submission:
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = ide_ele
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = i
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import random
    from math import log,ceil

    N=int(input())
    n=N

    A=list(map(int,input().split()))
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=10**25
    ope=[0 for i in range(N+1)]
    ope[N]=10**20

    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)
    #####ide_ele#####
    ide_ele = N
    #################


    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    rmq=SegTree(segfunc,ide_ele)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        S+=ope[i]
        B[i]+=ope[i]
    #print(time.time()-start)
    rmq=SegTree(segfunc,ide_ele)
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import random,time
from math import log,ceil


def four(a,b):
    if b>=a:
        return 0
    else:
        return ceil(a-b)


N=int(input())

A=list(map(int,input().split()))
start=time.time()
A=[log(A[i],4) for i in range(N)]
B=[A[-i-1] for i in range(N)]


#セグメント木
#####segfunc######
def segfunc(x,y):
    if x[0]>y[0]:
        return y
    elif x[0]<y[0]:
        return x
    else:
        return (x[0],min(x[1],y[1]))

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = (float("inf"),10**20)

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

Init=[[0,i] for i in range(N)]
for i in range(1,N):
    c=four(A[i-1],A[i])
    Init[i][0]+=c
    A[i]+=c

init(Init)

plu=[0]*N
plu[0]=sum(Init[i][0] for i in range(N))
S=plu[0]
zero=[N]

#A1 ... AnのBIT(1-indexed)
BIT = [0]*(n+1)
#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

for i in range(1,N):
    while i!=zero[-1]:
        k=query(i,zero[-1])[1]
        val=Init[k][0]+BIT_query(k+1)
        S-=val*(zero[-1]-i)
        BIT_update(i+1,-val)
        BIT_update(zero[-1]+1,val)
        zero.append(k)
    zero.pop()
    plu[i]=S

Init=[[0,i] for i in range(N)]
S=0
for i in range(1,N):
    c=max(0,ceil(B[i-1]-B[i]))
    Init[i][0]+=c
    S+=c
    B[i]+=c
#print(time.time()-start)
init(Init)
#print(time.time()-start)
neg=[0]*N
neg[0]=S
zero=[N]
check=[]
BIT=[0]*(n+1)

for i in range(1,N):
    while i!=zero[-1]:
        k=query(i,zero[-1])[1]
        val=Init[k][0]+BIT_query(k+1)
        S-=val*(zero[-1]-i)
        BIT_update(i+1,-val)
        BIT_update(zero[-1]+1,val)
        zero.append(k)
    zero.pop()
    neg[i]=S
#print(time.time()-start)
neg=neg[::-1]
for i in range(N):
    plu[i]*=2
    neg[i]=2*neg[i]+(i+1)

ans=min(neg[-1],plu[0])
for i in range(0,N-1):
    test=neg[i]+plu[i+1]
    ans=min(ans,test)

print(ans)

Fixed submission:
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = ide_ele
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = i
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import random
    from math import log,ceil

    N=int(input())
    n=N

    A=list(map(int,input().split()))
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=10**25
    ope=[0 for i in range(N+1)]
    ope[N]=10**20

    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)
    #####ide_ele#####
    ide_ele = N
    #################


    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    rmq=SegTree(segfunc,ide_ele)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        S+=ope[i]
        B[i]+=ope[i]
    #print(time.time()-start)
    rmq=SegTree(segfunc,ide_ele)
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def four(a,b):
    count=0
    while a>b:
        b*=4
        count+=1
    return count

N=int(input())
A=list(map(int,input().split()))
B=[A[-i-1] for i in range(N)]

#セグメント木
#####segfunc######
def segfunc(x,y):
    if x[0]>y[0]:
        return y
    elif x[0]<y[0]:
        return x
    else:
        return (x[0],min(x[1],y[1]))

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = (float("inf"),10**20)

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

Init=[[0,i] for i in range(N)]
for i in range(1,N):
    c=four(A[i-1],A[i])
    Init[i][0]+=c
    A[i]*=4**c

init(Init)

plu=[0]*N
plu[0]=sum(Init[i][0] for i in range(N))
S=plu[0]
zero=[N]

#A1 ... AnのBIT(1-indexed)
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

for i in range(1,N):
    while i!=zero[-1]:
        j=zero[-1]-1
        k=query(i,j+1)[1]
        val=Init[k][0]+BIT_query(k+1)
        S-=val*(j-i+1)
        BIT_update(i+1,-val)
        BIT_update(j+2,val)
        zero.append(k)
    zero.pop()
    plu[i]=S


Init=[[0,i] for i in range(N)]
for i in range(1,N):
    c=four(B[i-1],B[i])
    Init[i][0]+=c
    B[i]*=4**c

init(Init)

neg=[0]*N
neg[0]=sum(Init[i][0] for i in range(N))
S=neg[0]
zero=[N]

BIT=[0]*(n+1)

for i in range(1,N):
    while i!=zero[-1]:
        j=zero[-1]-1
        k=query(i,j+1)[1]
        val=Init[k][0]+BIT_query(k+1)
        S-=val*(j-i+1)
        BIT_update(i+1,-val)
        BIT_update(j+2,val)
        zero.append(k)
    zero.pop()
    neg[i]=S

neg=neg[::-1]
for i in range(N):
    plu[i]*=2
    neg[i]=2*neg[i]+(i+1)

ans=min(neg[-1],plu[0])
for i in range(0,N-1):
    test=neg[i]+plu[i+1]
    ans=min(ans,test)

print(ans)


Fixed submission:
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = ide_ele
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = i
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import random
    from math import log,ceil

    N=int(input())
    n=N

    A=list(map(int,input().split()))
    A=[log(A[i],4) for i in range(N)]
    B=[A[-i-1] for i in range(N)]
    memo=[0]*(N-1)
    ans=10**25
    ope=[0 for i in range(N+1)]
    ope[N]=10**20

    def segfunc(x,y):
        if ope[x]>ope[y]:
            return y
        elif ope[y]>ope[x]:
            return x
        else:
            return min(x,y)
    #####ide_ele#####
    ide_ele = N
    #################


    for i in range(1,N):
        ope[i]=max(0,ceil(A[i-1]-A[i]))
        A[i]+=ope[i]

    rmq=SegTree(segfunc,ide_ele)

    S=sum(ope[i] for i in range(N))
    ans=min(ans,2*S)
    zero=[N]

    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[i-1]+=2*S

    ope=[0 for i in range(N+1)]
    ope[N]=10**20
    S=0
    for i in range(1,N):
        ope[i]=max(0,ceil(B[i-1]-B[i]))
        S+=ope[i]
        B[i]+=ope[i]
    #print(time.time()-start)
    rmq=SegTree(segfunc,ide_ele)
    #print(time.time()-start)

    ans=min(ans,2*S+N)
    zero=[N]
    BIT=[0]*(n+1)

    for i in range(1,N):
        while i!=zero[-1]:
            k=rmq.query(i,zero[-1])
            val=ope[k]+BIT_query(k+1)
            S-=val*(zero[-1]-i)
            BIT_update(i+1,-val)
            BIT_update(zero[-1]+1,val)
            zero.append(k)
        zero.pop()
        memo[N-1-i]+=2*S+(N-i)
    #print(time.time()-start)
    test=min(memo)
    print(min(test,ans))

if __name__=="__main__":
    main()