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:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
def sub(a, minus=False):
    if minus:
        a = [-2*item for item in a]
    m = 20
    inf = 10**15
    dp = [[inf]*m for _ in range(n)] # i以降、a[i]に4^jをかけたところからソート
    for j in range(m):
        dp[-1][j] = j
    for i in range(n-2, -1, -1):
        if a[i]>a[i+1]:
            v = 0
            ai = a[i]; ai1 = a[i+1]
            while ai>ai1:
                ai1 *= 4
                v += 1
            for j in range(m):
                if j+v<m:
                    dp[i][j] = j + dp[i+1][j+v]
        else:
            v = 0
            ai = a[i]; ai1 = a[i+1]
            while True:
                ai *= 4
                if ai<=ai1:
                    v += 1
                else:
                    break
            for j in range(m):
                dp[i][j] = j + dp[i+1][max(0, j-v)]
    if minus:
        ans = [(2*min(dp[i][j] for j in range(m))+(n-i)) for i in range(n)]
    else:
        ans = [2*min(dp[i][j] for j in range(m)) for i in range(n)]
    return ans
dp0 = sub(list(a))
dp1 = sub([-item for item in a[::-1]], minus=True)[::-1]
dp0.append(0)
dp1.insert(0,0)
ans = min((dp0[i]+dp1[i]) for i in range(n+1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
def sub(a):
    dp = [0]*n
    amari = 0
    if a[-1]<0:
        dp[-1] = 1
        a[-1] *= -2
    for i in range(n-2, -1, -1):
        val = dp[i+1]
        if a[i]<0:
            val += 1
            a[i] *= -2
        if a[i]<=a[i+1]:
            dp[i] = val
            v0 = a[i]
            v1 = a[i+1]
            while True:
                v0 *= 4
                if v0<=v1:
                    amari += 2
                else:
                    break
        else:
            v0 = a[i]
            v1 = a[i+1]
            c = 0
            while v0>v1:
                v1 *= 4
                c += 2
            if c*(n-i-1)>=amari:
                dp[i] = val + c*(n-i-1) - amari
                amari = 0
            else:
                dp[i] = val
                amari -= c*(n-i-1)
#     print(a, dp)
    return dp
dp0 = sub(list(a))
dp1 = sub([-item for item in a[::-1]])[::-1]
dp0.append(0)
dp1.insert(0,0)
ans = min((dp0[i]+dp1[i]) for i in range(n+1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
def sub(a):
    dp = [0]*n
    amari = 0
    if a[-1]<0:
        dp[-1] = 1
        a[-1] *= -2
    for i in range(n-2, -1, -1):
        val = dp[i+1]
        if a[i]<0:
            val += 1
            a[i] *= -2
        if a[i]<=a[i+1]:
            dp[i] = val
            v0 = a[i]
            v1 = a[i+1]
            while True:
                v0 *= 4
                if v0<=v1:
                    amari += 1
                else:
                    break
        else:
            v0 = a[i]
            v1 = a[i+1]
            c = 0
            while v0>v1:
                v1 *= 4
                c += 2
            if c*(n-i-1)>=amari:
                dp[i] = val + c*(n-i-1) - amari
                amari = 0
            else:
                dp[i] = val
                amari -= c*(n-i-1)
#     print(a, dp)
    return dp
dp0 = sub(list(a))
dp1 = sub([-item for item in a[::-1]])[::-1]
dp0.append(0)
dp1.insert(0,0)
ans = min((dp0[i]+dp1[i]) for i in range(n+1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
def sub(a):
    dp = [0]*n
    if a[-1]<0:
        dp[-1] = 1
        a[-1] *= -2
    for i in range(n-2, -1, -1):
        val = dp[i+1]
        if a[i]<0:
            val += 1
            a[i] *= -2
        if a[i]<=a[i+1]:
            dp[i] = val
        else:
            v0 = a[i]
            v1 = a[i+1]
            c = 0
            while v0>v1:
                v1 *= 4
                c += 2
            dp[i] = val + c*(n-i-1)
#     print(a, dp)
    return dp
dp0 = sub(list(a))
dp1 = sub([-item for item in a[::-1]])[::-1]
dp0.append(0)
dp1.insert(0,0)
ans = min((dp0[i]+dp1[i]) for i in range(n+1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
def sub(a):
    dp = [0]*n
    if a[-1]<0:
        dp[-1] = 1
        a[-1] *= -2
    for i in range(n-2, -1, -1):
        val = dp[i+1]
        if a[i]<0:
            val += 1
            a[i] *= -2
        if a[i]<=a[i+1]:
            dp[i] = val
        else:
            v0 = a[i]
            v1 = a[i+1]
            c = 0
            while v0>v1:
                v1 *= 4
                c += 2
            dp[i] = val + c*(n-i-1)
    return dp
dp0 = sub(a)
dp1 = sub([-item for item in a[::-1]])[::-1]
dp0.append(0)
dp1.insert(0,0)
ans = min((dp0[i]+dp1[i]) for i in range(n+1))
print(ans)

Submission status: Wrong Answer

Solution code:
i=0
ans=0
N=int(input())
L=list(map(int,input().split()))
while True:
  if i==N-1:
    print(ans)
    exit()
  if L[i]>L[i+1]:
    ans+=1
    L[i]*=-2
  else:
    break#L[i+1]まではおっけー
  i+=1
for j in range(i+1,N):
  if L[j-1]>L[j]:
    while True:
      L[j]*=4
      ans+=2
      if L[j-1]<=L[j]:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
a = list(map(int,input().split()))

p = [0] * (n-1)
m = [0] * (n-1)

for i in range(n-1):
    x,y = a[i:i+2]
    cnt = 0
    if(x > y):
        while(x>y):
            y *= 4
            cnt += 2
    else:
        x *= 4
        while(x<=y):
            x*=4
            cnt -= 2
    p[i] = cnt

for i in range(n-1):
    x,y = a[i:i+2]
    cnt = 0
    if(x < y):
        while(x<y):
            x *= 4
            cnt += 2
    else:
        y *= 4
        while(x>=y):
            y*=4
            cnt -= 2
    m[i] = cnt

cumsum_p = [0] * (n+1)
cumsum_m = [0] * (n+1)

d = deque()
for i in range(n-2,-1,-1):
    cumsum_p[i] = cumsum_p[i+1]
    if(p[i] < 0):
        d.appendleft((i,p[i]))
    elif(p[i] > 0):
        cnt = p[i]
        while(d):
            j,rem_j = d.popleft()
            if(cnt + rem_j <= 0):
                cumsum_p[i] += (j-i) * cnt
                if(cnt + rem_j < 0):
                    d.appendleft((j,cnt + rem_j))
                cnt = 0
                break
            else:
                cumsum_p[i] += (j-i-1) * (-1 * rem_j)
                cnt = cnt + rem_j
        cumsum_p[i] += (n-i-1) * cnt

d = deque()
cumsum_m[1] = 1
for i in range(n-1):
    cumsum_m[i+2] = cumsum_m[i+1] + 1
    if(m[i] < 0):
        d.appendleft((i,m[i]))
    elif(m[i] > 0):
        cnt = m[i]
        while(d):
            j,rem_j = d.popleft()
            if( cnt + rem_j <= 0 ):
                cumsum_m[i+2] += (i-j) * cnt
                if( cnt + rem_j < 0):
                    d.appendleft((j,cnt + rem_j))
                cnt = 0
                break
            else:
                cumsum_m[i+2] += (j-i) * (-1*rem_j)
                cnt = cnt + rem_j
        cumsum_m[i+2] += (i+1) * cnt

ans = cumsum_p[0]
for i in range(n+1):
    ans = min(ans, cumsum_p[i] + cumsum_m[i])

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
a = list(map(int,input().split()))

# import random
# n = 7
# a = [random.randint(1, 100) for i in range(n)]

if(n==1):
    print(0)
    exit()

all_plus = [0] * n
all_minus = [0] * n

for i in range(1,n):
    cnt = 0
    if( a[i-1] <= a[i]):
        x = a[i-1] * 4
        while(x <= a[i]):
            x *= 4
            cnt -= 2
    else:
        x = a[i]
        while(a[i-1] > x):
            cnt += 2
            x *= 4
    all_plus[i-1] = cnt

for i in range(n-2,-1,-1):
    cnt = 0
    if( a[i] >= a[i+1]):
        x = a[i+1]*4
        while(a[i] >= x):
            x *= 4
            cnt -= 2
    else:
        x = a[i]
        while(x < a[i+1]):
            cnt += 2
            x *= 4
    all_minus[i] = cnt

cumsum_p = [0] * (n+1)
d = deque()
for i in range(n-2,-1,-1):
    cumsum_p[i] = cumsum_p[i+1]
    if(all_plus[i] < 0):
        d.appendleft((i,all_plus[i]))
    elif(all_plus[i] > 0):
        cnt = all_plus[i]
        while(d):
            j,num_j = d.popleft()
            cumsum_p[i] += cnt * (j-i)
            if(num_j + cnt < 0):
                d.appendleft((j,num_j+cnt))
                cnt = 0
                break
            else:
                cnt = num_j + cnt
        cumsum_p[i] += cnt * (n-1-i)

cumsum_m = [1] * (n)
d = deque()
for i in range(n-1):
    cumsum_m[i+1] = cumsum_m[i] + 1
    if(all_minus[i] < 0):
        d.appendleft((i,all_minus[i]))
    elif(all_minus[i] > 0):
        cnt = all_minus[i]
        while(d):
            j,num_j = d.popleft()
            cumsum_m[i+1] += cnt * (i-j)
            if(num_j + cnt < 0):
                d.appendleft((j,num_j+cnt))
                cnt = 0
                break
            else:
                cnt = num_j + cnt
        cumsum_m[i+1] += cnt * (i+1)
cumsum_m = [0] + cumsum_m


# print(a)
# print(all_plus)
# print(all_minus)
# print(cumsum_p)
# print(cumsum_m)

ans = min(cumsum_p[0], cumsum_m[-1])
for i in range(1,n):
    #minusの数がi個あるとする。
    tmp = cumsum_m[i] + cumsum_p[i]
    ans = min(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
a = list(map(int,input().split()))

if(n==1):
    print(0)
    exit()

all_plus = [0] * n
all_minus = [0] * n

for i in range(1,n):
    cnt = 0
    if( a[i-1] <= a[i]):
        x = a[i-1] * 4
        while(x <= a[i]):
            x *= 4
            cnt -= 2
    else:
        x = a[i]
        while(a[i-1] > x):
            cnt += 2
            x *= 4
    all_plus[i-1] = cnt

for i in range(n-2,-1,-1):
    cnt = 0
    if( a[i] >= a[i+1]):
        x = a[i+1]*4
        while(a[i] >= x):
            x *= 4
            cnt -= 2
    else:
        x = a[i]
        while(x < a[i+1]):
            cnt += 2
            x *= 4
    all_minus[i] = cnt

cumsum_p = [0] * (n+1)
d = deque()
for i in range(n-2,-1,-1):
    cumsum_p[i] = cumsum_p[i+1]
    if(all_plus[i] < 0):
        d.appendleft((i,all_plus[i]))
    elif(all_plus[i] > 0):
        point = i
        cnt = all_plus[i]
        while(d):
            j,num_j = d.popleft()
            cumsum_p[i] += cnt * (j-point)
            point = j
            if(num_j + cnt < 0):
                d.appendleft((j,num_j+cnt))
                cnt = 0
                break
            else:
                cnt = num_j + cnt
        cumsum_p[i] += cnt * (n-point-1)

cumsum_m = [1] * (n)
d = deque()
for i in range(n-1):
    cumsum_m[i+1] = cumsum_m[i] + 1
    if(all_minus[i] < 0):
        d.appendleft((i,all_minus[i]))
    elif(all_minus[i] > 0):
        point = i+1
        cnt = all_minus[i]
        while(d):
            j,num_j = d.popleft()
            cumsum_m[i+1] += cnt * (point-j)
            point = j
            if(num_j + cnt < 0):
                d.appendleft((j,num_j+cnt))
                cnt = 0
                break
            else:
                cnt = num_j + cnt
        cumsum_m[i+1] += cnt * point
cumsum_m = [0] + cumsum_m

ans = min(cumsum_p[0], cumsum_m[-1])
for i in range(1,n):
    #minusの数がi個あるとする。
    tmp = cumsum_m[i] + cumsum_p[i]
    ans = min(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))

if(n==1):
    print(0)
    exit()

all_plus = [0] * n
all_minus = [1] * n

for i in range(1,n):
    cnt = 0
    x = a[i]
    while(a[i-1] > x):
        cnt += 2
        x *= 4
    all_plus[i] = cnt + all_plus[i-1]

for i in range(n-2,-1,-1):
    cnt = 0
    x = a[i]
    while(x < a[i+1]):
        cnt += 2
        x *= 4
    all_minus[i] = cnt + all_minus[i+1]

cumsum_p = [0] * (n+1)
cumsum_m = [0] * (n+1)
for i in range(n):
    cumsum_p[n-1-i] = cumsum_p[n-i] + all_plus[n-1-i]
    cumsum_m[i+1] = cumsum_m[i] + all_minus[i]

ans = min(cumsum_p[0], cumsum_m[-1])
for i in range(1,n):
    #minusの数がi個あるとする。
    tmp = cumsum_m[i] - (all_minus[i-1]//2)*2*i
    tmp += cumsum_p[i] - (all_plus[i]//2)*2*(n-i)
    ans = min(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))

if(n==1):
    print(0)
    exit()

all_plus = [0] * n
all_minus = [1] * n

for i in range(1,n):
    cnt = 0
    x = a[i]
    while(a[i-1] > x):
        cnt += 2
        x *= 4
    all_plus[i] = cnt + all_plus[i-1]

for i in range(n-2,-1,-1):
    cnt = 0
    x = a[i]
    while(x < a[i+1]):
        cnt += 2
        x *= 4
    all_minus[i] = cnt + all_minus[i+1]

cumsum_p = [0] * (n+1)
cumsum_m = [0] * (n+1)
for i in range(n):
    cumsum_p[n-1-i] = cumsum_p[n-i] + all_plus[n-1-i]
    cumsum_m[i+1] = cumsum_m[i] + all_minus[i]

ans = min(cumsum_p[0], cumsum_m[-1])
for i in range(1,n):
    #minusの数がi個あるとする。
    tmp = cumsum_m[i] - (all_minus[i-1]//2)*2*i
    tmp += cumsum_p[i] - (all_plus[i]//2)*2*(n-i)
    print(i,tmp)
    ans = min(ans,tmp)

print(ans)

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)]
    D = [[0,0]for _ in range(N)]
    for i,[x1,y1,x2,y2] in enumerate(XY):
        D[i] = [math.atan2(y1,x1),math.atan2(y2,x2)]
    print(D)
    ans = 0
    for d1,d2 in D:
        cur = 0
        for dfr,dto in D:
            if dfr<=d1<=dto:
                cur += 1
        ans = max(ans,cur)



    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 = max(0, now + L[i] - R[i+1])
                if now%2==0:
                    now += 1
                cnt += now
            now = 0
            for i in range(x,N):
                if i!=x:
                    now = max(0, now + R[i] - L[i-1])
                cnt += now
            return cnt
        #print(f(0),f(1),f(2),f(3))

        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 = 0
        a1,a2 = A[i], A[i+1]
        while(a2>a1):
            cnt += 2
            a1 *= 4
        L[i] = cnt
    #print(R)
    #print(L)
    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

7
49 50 51 22 11 2 5
"""

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 = 0
        a1,a2 = A[i], A[i+1]
        while(a2>a1):
            cnt += 2
            a1 *= 4
        L[i] = cnt
    #print(R)
    #print(L)
    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

7
99 50 51 22 11 5 2
"""