Problem:


Score : 800 points

Problem Statement

There are N positive integers A_1, A_2, ..., A_N.
Takahashi can perform the following operation on these integers any number of times:

Choose 1 \leq i \leq N and multiply the value of A_i by -2.

Notice that he multiplies it by minus two.

He would like to make A_1 \leq A_2 \leq ... \leq A_N holds.
Find the minimum number of operations required. If it is impossible, print -1.

Constraints

1 \leq N \leq 200000

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the answer.

Sample Input 1

4
3 1 4 1

Sample Output 1

3

One possible solution is:

Choose i=4 and multiply the value of A_4 by -2. A_1, A_2, A_3, A_4 are now 3, 1, 4, -2.

Choose i=1 and multiply the value of A_1 by -2. A_1, A_2, A_3, A_4 are now -6, 1, 4, -2.

Choose i=4 and multiply the value of A_4 by -2. A_1, A_2, A_3, A_4 are now -6, 1, 4, 4.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

0

A_1 \leq A_2 \leq ... \leq A_N holds before any operation is performed.

Sample Input 3

8
657312726 129662684 181537270 324043958 468214806 916875077 825989291 319670097

Sample Output 3

7



Sample input:
4
3 1 4 1


Sample output:
3

Submission status: Wrong Answer

Solution code:
# ABC130
def examA():
    import numpy as np
    def powDetMod(n,arr,k,MOD=-1):
        repeat = 60
        local_doubling = [[] for _ in range(repeat+1)]
        local_doubling[0] = arr
        for i in range(repeat):
            local_doubling[i+1] = np.dot(local_doubling[i],local_doubling[i])
            if MOD>0:
                for h in range(n):
                    for w in range(n):
                        local_doubling[i+1][h][w] %= MOD
        now = [[1 if i==j else 0 for i in range(n)]for j in range(n)]
        for i in range(repeat+1):
            if k&(1<<i)>0:
                now = np.dot(now,local_doubling[i])
                if MOD > 0:
                    for h in range(n):
                        for w in range(n):
                            now[h][w] %= MOD
        return now
    L, A, B, M = LI()
    C = [0]*18
    cnt = L
    for i in range(18):
        if (pow(10,(i+1))-1-A)<0:
            continue
        C[i] = 1 + (pow(10,(i+1))-1-A)//B
        if (pow(10,i)-1-A)>=0:
            C[i] -= 1 + (pow(10,i)-1-A)//B
        if C[i]>=cnt:
            C[i] = cnt
            break
        cnt -= C[i]
    #print(C)
    X =  np.array([0,A,B])
    for i in range(18):
        now = [[pow(10,i+1,M),0,0],[1,1,0],[0,1,1]]
        now = np.array(now)
        arr = powDetMod(3,now,C[i],M)
        X = np.dot(X,arr)%M

    ans = X[0]%M
    print(ans)
    return

# ABC131
def examB():
    N = I()
    R = [inf,-inf]
    L = [inf,-inf]
    U = [inf,-inf]
    D = [inf,-inf]
    X = [inf,-inf]
    Y = [inf,-inf]
    for _ in range(N):
        x,y,s = LSI()
        x,y = int(x),int(y)
        if s=="R":
            if x<R[0]: R[0] = x
            if x>R[1]: R[1] = x
            if y<Y[0]: Y[0] = y
            if y>Y[1]: Y[1] = y
        elif s=="L":
            if x<L[0]: L[0] = x
            if x>L[1]: L[1] = x
            if y<Y[0]: Y[0] = y
            if y>Y[1]: Y[1] = y
        elif s=="U":
            if y<U[0]: U[0] = y
            if y>U[1]: U[1] = y
            if x<X[0]: X[0] = x
            if x>X[1]: X[1] = x
        elif s=="D":
            if y<D[0]: D[0] = y
            if y>D[1]: D[1] = y
            if x<X[0]: X[0] = x
            if x>X[1]: X[1] = x
    def calc_area(t):
        x = max(R[1]+t,L[1]-t,X[1])-min(R[0]+t,L[0]-t,X[0])
        y = max(U[1]+t,D[1]-t,Y[1])-min(U[0]+t,D[0]-t,Y[0])
        if x<=0 or y<=0:
            return 0
        return x*y
    ans = calc_area(0)
    for i in [0,1]:
        for j in [0,1]:
            if R[i] <= X[j]:
                T = (X[j] - R[i])
                ans = min(ans, calc_area(T))
            if L[i] >= X[j]:
                T = (L[i] - X[j])
                ans = min(ans, calc_area(T))
            if R[i] <= L[j]:
                T = dec((L[j] - R[i]) / 2)
                ans = min(ans, calc_area(T))

            if U[i] <= Y[j]:
                T = (Y[j] - U[i])
                ans = min(ans, calc_area(T))
            if D[i] >= Y[j]:
                T = (D[i] - Y[j])
                ans = min(ans, calc_area(T))
            if U[i] <= D[j]:
                T = dec((D[j] - U[i]) / 2)
                ans = min(ans, calc_area(T))

    print(ans)
    return


def examC():
    N = I()
    XY = [LI()for _ in range(4)]

    return

def examD():
    def ternarySearch(A,k):
        def f(x):
            cnt = 0
            now = 1
            for i in range(x)[::-1]:
                if i!=x-1:
                    now += L[i]
                if now%2==0:
                    now += 1
                cnt += now
            now = 0
            for i in range(x,N):
                if i!=x:
                    now += R[i]
                cnt += now
            return cnt

        fr, to = 0, k
        while to - fr > 4:
            x1, x2 = (2 * fr + to) // 3, (2 * to + fr) // 3
            f1, f2 = f(x1), f(x2)
            if f1 < f2:
                to = x2
            elif f1 > f2:
                fr = x1
            else:
                fr, to = x1, x2
            #print(fr,to,x1,x2)
            #input()
        rep = inf
        for i in range(fr,to+1):
            rep = min(rep,f(i))
        return rep
    N = I()
    A = LI()
    flag = True
    for i in range(N-1):
        if A[i+1]>=A[i]:
            continue
        flag = False
    if flag:
        print(0)
        return
    R = [0]*N
    L = [0]*N
    for i in range(1,N):
        cnt = 0
        a1,a2 = A[i-1],A[i]
        while(a2<a1):
            cnt += 2
            a2 *= 4
        R[i] = cnt
    for i in range(N-1):
        cnt = 1
        a1,a2 = A[i]*2, A[i+1]
        while(a2>a1):
            cnt += 2
            a1 *= 4
        L[i] = cnt
    ans = ternarySearch(A,N)
    print(ans)

    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def f(x, y):
  res = 0
  while x < y:
    x *= 4
    res += 1
  return res
n = int(input())
A = list(map(int, input().split()))
L = [0]*n
R = [0]*n
for i in range(n-1):
  l = f(A[i], A[i+1])
  L[i+1] = L[i]+2*l*(i+1)
  r = f(A[n-1-i], A[n-2-i])
  R[n-2-i] = R[n-1-i]+2*r*(i+1)
ans = min(n+L[-1], R[0])
for i in range(n-1):
  temp = (i+1) + L[i]+R[i+1]
  ans = min(ans, temp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def f(x, y):
  res = 0
  while x < y:
    x *= 4
    res += 1
  return res
n = int(input())
A = list(map(int, input().split()))
L = [0]*n
R = [0]*n
for i in range(n-1):
  l = f(A[i], A[i+1])
  L[i+1] = L[i]+l*(i+1)
  r = f(A[n-1-i], A[n-2-i])
  R[n-2-i] = R[n-1-i]+r*(i+1)
ans = min(n+2*L[-1], 2*R[0])
for i in range(n-1):
  temp = (i+1) + 2*(L[i]+R[i+1])
  ans = min(ans, temp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def f(x, y):
  res = 0
  while x < y:
    x *= 4
    res += 1
  return res
n = int(input())
A = list(map(int, input().split()))
L = [0]*n
R = [0]*n
for i in range(n-1):
  l = f(A[i], A[i+1])
  L[i+1] = L[i]+l*(i+1)
  r = f(A[n-1-i], A[n-2-i])
  R[n-2-i] = R[n-1-i]+r*(i+1)
ans = min(n+2*L[-1], 2*R[0])
for i in range(1, n-1):
  temp = 2*(L[i-1]+R[i])+i
  ans = min(ans, temp)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  ret = 0
  while x > y:
    y *= 4
    ret += 1
  return ret
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(ls[-1],1)]
  for i in range(l-1)[::-1]:
    sm = 0
    ret[i] += ret[i+1]
    x = ls[i]
    while stack and x >= stack[-1][0]:
      val,num = stack.pop()
      d = d4(x,val)
      sm += num
      ret[i] += d*num
      x = val*(4**d)
    if stack and x < stack[-1][0]:
      stack.append((x,sm))
      sm = 0
    elif not stack:
      stack.append((x,sm))
      sm = 0
    stack.append((ls[i],sm+1))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] *= 2
  cn[i] += n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  ret = 0
  while x > y:
    y *= 4
    ret += 1
  return ret
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(ls[-1],1)]
  for i in range(l-1)[::-1]:
    sm = 0
    ret[i] += ret[i+1]
    x = ls[i]
    while stack and x >= stack[-1][0]:
      val,num = stack.pop()
      d = d4(x,val)
      sm += num
      ret[i] += d*num
      x = val*(4**d)
    if stack and sm and x < stack[-1][0]:
      stack.append((x,sm))
      sm = 0
    stack.append((ls[i],sm+1))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] *= 2
  cn[i] += n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  ret = 0
  while x > y:
    y *= 4
    ret += 1
  return ret
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(ls[-1],1)]
  for i in range(l-1)[::-1]:
    sm = 0
    ret[i] += ret[i+1]
    x = ls[i]
    while stack and x >= stack[-1][0]:
      val,num = stack.pop()
      d = d4(x,val)
      sm += num
      ret[i] += d*num
      x = val*(4**d)
    if not stack or x < stack[-1][0]:
      stack.append((x,sm))
      sm = 0
    stack.append((ls[i],sm+1))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] *= 2
  cn[i] += n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  ret = 0
  while x > y:
    y *= 4
    ret += 1
  return ret
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(ls[-1],1)]
  for i in range(l-1)[::-1]:
    sm = 0
    ret[i] += ret[i+1]
    x = ls[i]
    while stack and x*4 >= stack[-1][0]:
      val,num = stack.pop()
      d = d4(x,val)
      sm += num
      ret[i] += d*num
      x = val*(4**d)
    stack.append((ls[i],sm+1))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] *= 2
  cn[i] += n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  if x >= y:
    ret = 0
    while x > y:
      y *= 4
      ret += 1
    return ret
  else:
    print(2/0)
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(ls[-1],1)]
  for i in range(l-1)[::-1]:
    sm = 0
    ret[i] += ret[i+1]
    x = ls[i]
    while stack and x >= stack[-1][0]:
      val,num = stack.pop()
      d = d4(x,val)
      sm += num
      ret[i] += d*num
      x = val*(4**d)
    if stack and x < stack[-1][0]:
      stack.append((x,sm))
      sm = 0
    stack.append((ls[i],sm+1))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] *= 2
  cn[i] += n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  if x >= y:
    ret = 0
    while x > y:
      y *= 4
      ret += 1
    return ret
  else:
    print(2/0)
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(ls[-1],1)]
  for i in range(l-1)[::-1]:
    sm = 0
    ret[i] += ret[i+1]
    x = ls[i]
    while stack and x >= stack[-1][0]:
      val,num = stack.pop()
      d = d4(x,val)
      sm += num
      ret[i] += d*num
      x = val*(4**d)
    stack.append((ls[i],sm+1))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] *= 2
  cn[i] += n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  if x >= y:
    ret = 0
    while x > y:
      y *= 4
      ret += 1
    return ret
  else:
    print(2/0)
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(ls[-1],1)]
  for i in range(l-1)[::-1]:
    sm = 0
    ret[i] += ret[i+1]
    x = ls[i]
    while stack and x >= stack[-1][0]:
      val,num = stack.pop()
      d = d4(x,val)
      sm += num
      ret[i] += d*num
      x = val*(4**d)
    stack.append((ls[i],sm+1))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] = cn[i]*2+n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  if x > y:
    ret = 0
    while x > y:
      y *= 4
      ret += 1
    return ret
  else:
    print(2/0)
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(ls[-1],1)]
  for i in range(l-1)[::-1]:
    sm = 0
    ret[i] += ret[i+1]
    x = ls[i]
    while stack and x > stack[-1][0]:
      val,num = stack.pop()
      d = d4(x,val)
      sm += num
      ret[i] += d*num
      x = val*(4**d)
    stack.append((ls[i],sm+1))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] = cn[i]*2+n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  if x > y:
    ret = 0
    while x > y:
      y *= 4
      ret += 1
    return ret
  else:
    ret = 1
    while x <= y:
      x *= 4
      ret -= 1
    return ret
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(ls[-1],1)]
  for i in range(l-1)[::-1]:
    sm = 0
    ret[i] += ret[i+1]
    x = ls[i]
    while stack and x > stack[-1][0]:
      val,num = stack.pop()
      d = d4(x,val)
      sm += num
      ret[i] += d*num
      x = val*(4**d)
    stack.append((ls[i],sm+1))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] = cn[i]*2+n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  if x > y:
    ret = 0
    while x > y:
      y *= 4
      ret += 1
    return ret
  else:
    ret = 1
    while x <= y:
      x *= 4
      ret -= 1
    return ret
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(ls[-1],1)]
  for i in range(l-1)[::-1]:
    sm = 0
    ret[i] += ret[i+1]
    x = ls[i]
    while stack and x > stack[-1][0]:
      val,num = stack.pop()
      d = d4(x,val)
      sm += num
      ret[i] += d*num
      x = val*4**d
    stack.append((ls[i],sm+1))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] = cn[i]*2+n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  if x > y:
    ret = 0
    while x > y:
      y *= 4
      ret += 1
    return ret
  else:
    ret = 1
    while x <= y:
      x *= 4
      ret -= 1
    return ret
def cost(ls):
  l = len(ls)
  ret = [0]*l
  stack = [(ls[-1],1)]
  for i in range(l-1)[::-1]:
    sm = 1
    ret[i] += ret[i+1]
    while stack and ls[i] > stack[-1][0]:
      val,num = stack.pop()
      ret[i] += d4(ls[i],val)*num
      sm += num
    stack.append((ls[i],sm))
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] = cn[i]*2+n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  if x == y:
    return 0
  if x > y:
    ret = 0
    while x > y:
      y *= 4
      ret += 1
    return ret
  else:
    ret = 1
    while x <= y:
      x *= 4
      ret -= 1
    return ret
def cost(ls):
  l = len(ls)
  ret = [0]*l
  tmp = 0
  for i in range(l-1)[::-1]:
    if ls[i] <= ls[i+1]:
      tmp += d4(ls[i],ls[i+1])*(l-i-1)
      ret[i] = ret[i+1]
    else:
      ret[i] = tmp+ret[i+1]+d4(ls[i],ls[i+1])*(l-i-1)
      tmp = 0
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] = cn[i]*2+n-i
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
def d4(x,y):
  if x == y:
    return 0
  if x > y:
    ret = 0
    while x > y:
      y *= 4
      ret += 1
    return ret
  else:
    ret = 1
    while x <= y:
      x *= 4
      ret -= 1
    return ret
def cost(ls):
  l = len(ls)
  ret = [0]*l
  tmp = 0
  for i in range(l-1)[::-1]:
    if ls[i] <= ls[i+1]:
      tmp += d4(ls[i],ls[i+1])*(l-i-1)
      ret[i] = ret[i+1]
    else:
      ret[i] = tmp+ret[i+1]+d4(ls[i],ls[i+1])*(l-i-1)
      tmp = 0
  return ret
cp = cost(a)
cn = cost(a[::-1])
for i in range(n):
  cp[i] *= 2
  cn[i] = cn[i]*2+1
ansls = [cp[0],cn[0]]
for i in range(1,n):
  ansls.append(cp[i]+cn[n-i])
print(min(ansls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(reversed(a))
c = [0] * (n + 1)
d = [0] * (n + 1)
s = [(0, 10 ** 30)]
res = 0
for i in range(1, n):
    if a[i - 1] < a[i] * 4:
        t = a[i - 1]
        cnt = 0
        while t < a[i]:
            cnt += 1
            t *= 4
        while cnt > 0:
            idx, p = s.pop()
            if cnt >= p:
                res += p * (i - idx)
                cnt -= p
            else:
                res += cnt * (i - idx)
                cnt = 0
                s.append((idx, p - cnt))
    else:
        t = a[i]
        cnt = 0
        while a[i - 1] >= t * 4:
            t *= 4
            cnt += 1
        s.append((i, cnt))
    c[i + 1] = res
s = [(0, 10 ** 30)]
res = 0
for i in range(1, n):
    if b[i - 1] < b[i] * 4:
        t = b[i - 1]
        cnt = 0
        while t < b[i]:
            cnt += 1
            t *= 4
        while cnt > 0:
            idx, p = s.pop()
            if cnt >= p:
                res += p * (i - idx)
                cnt -= p
            else:
                res += cnt * (i - idx)
                cnt = 0
                s.append((idx, p - cnt))
    else:
        t = b[i]
        cnt = 0
        while b[i - 1] >= t * 4:
            t *= 4
            cnt += 1
        s.append((i, cnt))
    d[i + 1] = res
ans = float('inf')
for i in range(n + 1):
    ans = min(ans, (c[i] + d[n - i]) * 2 + i)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(reversed(a))
c = [0] * (n + 1)
d = [0] * (n + 1)
s = [(0, 10 ** 18)]
res = 0
for i in range(1, n):
    if a[i - 1] < a[i] * 4:
        t = a[i - 1]
        cnt = 0
        while t < a[i]:
            cnt += 1
            t *= 4
        while cnt > 0:
            idx, p = s.pop()
            if cnt >= p:
                res += p * (i - idx)
                cnt -= p
            else:
                res += cnt * (i - idx)
                cnt = 0
                s.append((idx, p - cnt))
    else:
        t = a[i]
        cnt = 0
        while a[i - 1] >= t * 4:
            t *= 4
            cnt += 1
        s.append((i, cnt))
    c[i + 1] = res
s = [(0, 10 ** 18)]
res = 0
for i in range(1, n):
    if b[i - 1] < b[i] * 4:
        t = b[i - 1]
        cnt = 0
        while t < b[i]:
            cnt += 1
            t *= 4
        while cnt > 0:
            idx, p = s.pop()
            if cnt >= p:
                res += p * (i - idx)
                cnt -= p
            else:
                res += cnt * (i - idx)
                cnt = 0
                s.append((idx, p - cnt))
    else:
        t = b[i]
        cnt = 0
        while b[i - 1] >= t * 4:
            t *= 4
            cnt += 1
        s.append((i, cnt))
    d[i + 1] = res
ans = 10 ** 18
for i in range(n + 1):
    ans = min(ans, (c[i] + d[n - i]) * 2 + i)
print(ans)

Submission status: Wrong Answer

Solution code:
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=[random.randint(1,10**9) for i in range(N)]
    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()

Submission status: Wrong Answer

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

    N=int(input())

    A=[random.randint(1,10**9) for i in range(N)]
    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()

Submission status: Wrong Answer

Solution code:
def main():
    import random,time
    from math import log,ceil
    
    N=int(input())
    
    A=[random.randint(1,10**9) for i in range(N)]
    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()

Submission status: Wrong Answer

Solution code:
def four(a,b):
    count=0
    while a>b:
        b*=4
        count+=1
    return count

N=int(input())
A=list(map(int,input().split()))

neg=[0]*N
neg[0]=1
for i in range(1,N):
    a,b=A[i],A[i-1]
    c=four(a,b)
    neg[i]=1+neg[i-1]+2*c*i

plu=[0]*N
plu[-1]=0
for i in range(N-2,-1,-1):
    a,b=A[i],A[i+1]
    c=four(a,b)
    plu[i]=plu[i+1]+2*c*(N-i-1)

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