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:
INF = 10**10
n = int(input())
a = list(map(int, input().split()))

dp_fr = [[INF for _ in range(20)] for _ in range(n)]
dp_ba = [[INF for _ in range(20)] for _ in range(n)]

#dp[i][j]: iまで考えてa_iを4^j倍したときの必要最小コスト
for j in range(20):
	dp_fr[0][j] = 2*j

for i in range(1, n):
	if a[i-1] < a[i]:
		k = 0
		while a[i-1] * pow(4, k) < a[i]:
			k += 1
		for j in range(20):
			if j+k < 20:
				dp_fr[i][j] = 2*j + dp_fr[i-1][j+k]
			else:
				dp_fr[i][j] = 2*j + dp_fr[i-1][19] + 2*(i+1) * (j+k-19)
	else:
		k = 0
		while a[i-1] >= a[i] * pow(4, k+1):
			k += 1
		for j in range(20):
			dp_fr[i][j] = 2*j + dp_fr[i-1][max(j-k, 0)]

for j in range(20):
	dp_ba[n-1][j] = 2*j

for i in range(n-2, -1, -1):
	if a[i+1] < a[i]:
		k = 0
		while a[i+1] * pow(4, k) < a[i]:
			k += 1
		for j in range(20):
			if j+k < 20:
				dp_ba[i][j] = 2*j + dp_ba[i+1][j+k]
			else:
				dp_ba[i][j] = 2*j + dp_ba[i+1][19] + 2*(n-i-1) * (j+k-19)
	else:
		k = 0
		while a[i+1] >= a[i] * pow(4, k+1):
			k += 1
		for j in range(20):
			dp_ba[i][j] = 2*j + dp_ba[i+1][max(j-k, 0)]

#print(*dp_fr, sep="\n")
#print(*dp_ba, sep="\n")

ans = min(dp_ba[0][0], n + dp_fr[n-1][0])
for i in range(n-1):
	ans = min(ans, dp_ba[i+1][0] + i+1 + dp_fr[i][0])

print(ans)

Submission status: Wrong Answer

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

dp_fr = [[INF for _ in range(20)] for _ in range(n)]
dp_ba = [[INF for _ in range(20)] for _ in range(n)]

#dp[i][j]: iまで考えてa_iを4^j倍したときの必要最小コスト
for j in range(20):
	dp_fr[0][j] = 2*j

for i in range(1, n):
	if a[i-1] < a[i]:
		k = 0
		while a[i-1] * pow(4, k) < a[i]:
			k += 1
		for j in range(20):
			if j+k < 20:
				dp_fr[i][j] = 2*j + dp_fr[i-1][j+k]
	else:
		k = 0
		while a[i-1] >= a[i] * pow(4, k+1):
			k += 1
		for j in range(20):
			dp_fr[i][j] = 2*j + dp_fr[i-1][max(j-k, 0)]

for j in range(20):
	dp_ba[n-1][j] = 2*j

for i in range(n-2, -1, -1):
	if a[i+1] < a[i]:
		k = 0
		while a[i+1] * pow(4, k) < a[i]:
			k += 1
		for j in range(20):
			if j+k < 20:
				dp_ba[i][j] = 2*j + dp_ba[i+1][j+k]
	else:
		k = 0
		while a[i+1] >= a[i] * pow(4, k+1):
			k += 1
		for j in range(20):
			dp_ba[i][j] = 2*j + dp_ba[i+1][max(j-k, 0)]

#print(*dp_fr, sep="\n")
#print(*dp_ba, sep="\n")

ans = min(dp_ba[0][0], n + dp_fr[n-1][0])
for i in range(n-1):
	ans = min(ans, dp_ba[i+1][0] + i+1 + dp_fr[i][0])

print(ans)

Submission status: Wrong Answer

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

dp_fr = [[INF for _ in range(20)] for _ in range(n)]
dp_ba = [[INF for _ in range(20)] for _ in range(n)]

#dp[i][j]: iまで考えてa_iを4^j倍したときの必要最小コスト
for j in range(20):
	dp_fr[0][j] = 2*j

for i in range(1, n):
	if a[i-1] < a[i]:
		k = 0
		while a[i-1] * pow(4, k) < a[i]:
			k += 1
		for j in range(20):
			if j+k < 20:
				dp_fr[i][j] = 2*j + dp_fr[i-1][j+k]
	else:
		k = 0
		while a[i-1] >= a[i] * pow(4, k):
			k += 1
		for j in range(20):
			dp_fr[i][j] = 2*j + dp_fr[i-1][max(j-k, 0)]

for j in range(20):
	dp_ba[n-1][j] = 2*j

for i in range(n-2, -1, -1):
	if a[i+1] < a[i]:
		k = 0
		while a[i+1] * pow(4, k) < a[i]:
			k += 1
		for j in range(20):
			if j+k < 20:
				dp_ba[i][j] = 2*j + dp_ba[i+1][j+k]
	else:
		k = 0
		while a[i+1] >= a[i] * pow(4, k):
			k += 1
		for j in range(20):
			dp_ba[i][j] = 2*j + dp_ba[i+1][max(j-k, 0)]

ans = min(dp_ba[0][0], n + dp_fr[n-1][0])
for i in range(n-1):
	ans = min(ans, dp_ba[i+1][0] + i+1 + dp_fr[i][0])

print(ans)

Submission status: Wrong Answer

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

dp_fr = [[INF for _ in range(20)] for _ in range(n)]
dp_ba = [[INF for _ in range(20)] for _ in range(n)]

#dp[i][j]: iまで考えてa_iを4^j倍したときの必要最小コスト
for j in range(20):
	dp_fr[0][j] = 2*j

for i in range(1, n):
	k = -20
	while a[i-1] * pow(4, k) < a[i]:
		k += 1
	for j in range(20):
		if j+k < 20:
			dp_fr[i][j] = 2*j + dp_fr[i-1][max(j+k, 0)]

for j in range(20):
	dp_ba[n-1][j] = 2*j

for i in range(n-2, -1, -1):
	k = -20
	while a[i+1] * pow(4, k) < a[i]:
		k += 1
	for j in range(20):
		if j+k < 20:
			dp_ba[i][j] = 2*j + dp_ba[i+1][max(j+k, 0)]

ans = min(dp_ba[0][0], n + dp_fr[n-1][0])
for i in range(n-1):
	ans = min(ans, dp_ba[i+1][0] + i+1 + dp_fr[i][0])

print(ans)

Submission status: Wrong Answer

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

dp_fr = [[INF for _ in range(40)] for _ in range(n)]
dp_ba = [[INF for _ in range(40)] for _ in range(n)]

#dp[i][j]: iまで考えてa_iを4^j倍したときの必要最小コスト
for j in range(40):
	dp_fr[0][j] = 2*j

for i in range(1, n):
	k = 0
	while a[i-1] * pow(4, k) < a[i]:
		k += 1
	for j in range(40):
		if j+k < 40:
			dp_fr[i][j] = 2*j + dp_fr[i-1][j+k]

for j in range(40):
	dp_ba[n-1][j] = 2*j

for i in range(n-2, -1, -1):
	k = 0
	while a[i+1] * pow(4, k) < a[i]:
		k += 1
	for j in range(40):
		if j+k < 40:
			dp_ba[i][j] = 2*j + dp_ba[i+1][j+k]

ans = min(dp_ba[0][0], n + dp_fr[n-1][0])
for i in range(n-1):
	ans = min(ans, dp_ba[i+1][0] + i+1 + dp_fr[i][0])

print(ans)

Submission status: Wrong Answer

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

dp_fr = [[INF for _ in range(20)] for _ in range(n)]
dp_ba = [[INF for _ in range(20)] for _ in range(n)]

#dp[i][j]: iまで考えてa_iを4^j倍したときの必要最小コスト
for j in range(20):
	dp_fr[0][j] = 2*j

for i in range(1, n):
	k = 0
	while a[i-1] * pow(4, k) < a[i]:
		k += 1
	for j in range(20):
		if j+k < 20:
			dp_fr[i][j] = 2*j + dp_fr[i-1][j+k]

for j in range(20):
	dp_ba[n-1][j] = 2*j

for i in range(n-2, -1, -1):
	k = 0
	while a[i+1] * pow(4, k) < a[i]:
		k += 1
	for j in range(20):
		if j+k < 20:
			dp_ba[i][j] = 2*j + dp_ba[i+1][j+k]

ans = min(dp_ba[0][0], n + dp_fr[n-1][0])
for i in range(n-1):
	ans = min(ans, dp_ba[i+1][0] + i+1 + dp_fr[i][0])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
dpl = [0] * (N + 1)
h = []
for i in range(N):
  x = a[i] * 2
  if len(h):
    while h[0] < x:
      hpush(h, hpop(h) * 4)
      dpl[i + 1] += 2
  hpush(h, x)
  dpl[i + 1] += dpl[i] + 1

a.reverse()
dpr = [0] * (N + 1)
h = []
for i in range(N):
  x = a[i]
  if len(h):
    while -h[0] > x:
      x *= 4
      dpr[i + 1] += 2
  hpush(h, -x)
  dpr[i + 1] += 1

res = float("inf")
for i in range(N):
  res = min(res, dpl[i] + dpr[N - i])
print(res)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    def f(a, b):
        ret = 0
        while a > b:
            ret += 2
            b *= 4
        return ret

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

    right = [0] * (N+1)
    st = [(1, A[-1], A[-1])]
    for i in range(N-2, -1, -1):
        a = A[i]
        st.append((1, a, a))
        right[i] = right[i+1]
        while True:
            if len(st) == 1:
                break
            if st[-1][2] > st[-2][1]:
                na, amin, amax = st.pop()
                nb, bmin, bmax = st.pop()
                k = f(amax, bmin)
                right[i] += nb * k
                if st:
                    st.append((na+nb, amin, bmax << k))
                else:
                    st.append((na+nb, amin, float("inf")))
            else:
                break
    left = [0] * (N+1)
    left[1] = 1
    st = [(1, A[0], A[0])]
    for i in range(2, N+1):
        a = A[i-1]
        st.append((1, a, a))
        left[i] = left[i-1] + 1
        while True:
            if len(st) == 1:
                break
            if st[-1][2] > st[-2][1]:
                na, amin, amax = st.pop()
                nb, bmin, bmax = st.pop()
                k = f(amax, bmin)
                left[i] += nb * k
                if st:
                    st.append((na + nb, amin, bmax << k))
                else:
                    st.append((na+nb, amin, float("inf")))
            else:
                break
    ans = 10**10
    for i in range(N+1):
        ans = min(ans, left[i] + right[i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    def f(a, b):
        ret = 0
        while a > b:
            ret += 2
            b *= 4
        return ret

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

    right = [0] * (N+1)
    st = [(1, A[-1], A[-1])]
    for i in range(N-2, -1, -1):
        a = A[i]
        st.append((1, a, a))
        right[i] = right[i+1]
        while True:
            if len(st) == 1:
                break
            if st[-1][2] > st[-2][1]:
                na, amin, amax = st.pop()
                nb, bmin, bmax = st.pop()
                k = f(amax, bmin)
                right[i] += nb * k
                st.append((na+nb, amin, bmax * (1<<k)))
            else:
                break
    left = [0] * (N+1)
    left[1] = 1
    st = [(1, A[0], A[0])]
    for i in range(2, N+1):
        a = A[i-1]
        st.append((1, a, a))
        left[i] = left[i-1] + 1
        while True:
            if len(st) == 1:
                break
            if st[-1][2] > st[-2][1]:
                na, amin, amax = st.pop()
                nb, bmin, bmax = st.pop()
                k = f(amax, bmin)
                left[i] += nb * k
                st.append((na + nb, amin, bmax * (1 << k)))
            else:
                break
    ans = 10**10
    for i in range(N+1):
        ans = min(ans, left[i] + right[i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    def f(a, b):
        ret = 0
        while a > b:
            ret += 2
            b *= 4
        return ret

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

    right = [0] * (N+1)
    st = [(1, A[-1], A[-1])]
    for i in range(N-2, -1, -1):
        a = A[i]
        st.append((1, a, a))
        right[i] = right[i+1]
        while True:
            if len(st) == 1:
                break
            if st[-1][2] > st[-2][1]:
                na, amin, amax = st.pop()
                nb, bmin, bmax = st.pop()
                k = f(amax, bmin)
                right[i] += nb * k
                st.append((na+nb, amin, min(bmax * (1<<k), 10**10)))
            else:
                break
    left = [0] * (N+1)
    left[1] = 1
    st = [(1, A[0], A[0])]
    for i in range(2, N+1):
        a = A[i-1]
        st.append((1, a, a))
        left[i] = left[i-1] + 1
        while True:
            if len(st) == 1:
                break
            if st[-1][2] > st[-2][1]:
                na, amin, amax = st.pop()
                nb, bmin, bmax = st.pop()
                k = f(amax, bmin)
                left[i] += nb * k
                st.append((na + nb, amin, min(bmax * (1 << k), 10 ** 10)))
            else:
                break
    ans = 10**10
    for i in range(N+1):
        ans = min(ans, left[i] + right[i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/caddi2018/tasks/caddi2018_c

まさか、3分探索か？？？
正負が変わる位置を決め撃ったら、あとは貪欲に決まる
正負が変わる位置を1だけ右に変更したとする
すると、基準点より左は回数は単調増加し、右は単調減少する

→3分探索可能そう！！
数字がでかくなりすぎるから根本的な問題か？
C++だと longlongを突破しそう…

4を何回掛ければ左の数以上になるか、を持っておく？
3回のとき、
左に4**N がかかっていれば、4**(N+3)を掛けて対応できる

おなじになるとき、逆向きは-xにしておけばよい
そうでないときは-x+1でおｋ

3分探索が誤りぽさそう？
だとしたら全探索の高速化にかじを切る必要がある

===答えを見た===

いまいち実装がわからない
S[x][i] = i+S[x+1][?]
?が15以上は15から求められる

"""

N = int(input())
A = list(map(int,input().split()))
four = [1]
for i in range(100):
    four.append(four[-1] * 4)

LS = []
for i in range(N):

    if i == 0:
        now = [i for i in range(16)]
    else:
        now = []

        for j in range(16):

            l = -1
            r = 100

            while r-l != 1:
                m = (l+r)//2
                if A[i-1] * four[m] >= A[i] * four[j]:
                    r = m
                else:
                    l = m

            if r <= 15:
                now.append(LS[-1][r] + j)
            else:
                now.append(LS[-1][15] + i*(r-15 + r-15+i-1)//2 + j)
        
    LS.append(now)

A.reverse()
RS = []

for i in range(N):

    if i == 0:
        now = [i for i in range(16)]
    else:
        now = []

        for j in range(16):

            l = -1
            r = 40

            while r-l != 1:
                m = (l+r)//2
                if A[i-1] * four[m] >= A[i] * four[j]:
                    r = m
                else:
                    l = m

            if r <= 15:
                now.append(RS[-1][r] + j)
            else:
                now.append(RS[-1][15] + i*(r-15 + r-15+i-1)//2 + j)
        
    RS.append(now)
RS.reverse()

#print (LS)
#print (RS)

ans = float("inf")

for i in range(N+1):

    if i == 0:
        nn = RS[0][0] * 2
    elif i == N:
        nn = N+LS[-1][0] * 2
    else:
        nn = RS[i][0]*2 + i + LS[i-1][0]*2

    #print (nn)
    ans = min(nn,ans)

print (ans)

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/caddi2018/tasks/caddi2018_c

まさか、3分探索か？？？
正負が変わる位置を決め撃ったら、あとは貪欲に決まる
正負が変わる位置を1だけ右に変更したとする
すると、基準点より左は回数は単調増加し、右は単調減少する

→3分探索可能そう！！
数字がでかくなりすぎるから根本的な問題か？
C++だと longlongを突破しそう…

4を何回掛ければ左の数以上になるか、を持っておく？
3回のとき、
左に4**N がかかっていれば、4**(N+3)を掛けて対応できる

おなじになるとき、逆向きは-xにしておけばよい
そうでないときは-x+1でおｋ
"""

def want(ind):

    ret = 0

    now = 0
    for i in range(ind+1,N):
        now = max(0,now+lmul[i])
        ret += now*2
    
    now = 0
    for i in range(ind-1,-1,-1):
        ret += 1
        if i == ind-1:
            continue
        now = max(0,now+rmul[i])
        ret += now*2        

    return ret

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

lmul = [0]
rmul = []

for i in range(N-1):
    L = a[i]
    R = a[i+1]

    if L >= R:
        num = 0
        while R < L:
            R *= 4
            num += 1

        lmul.append(num)

        if R==L:
            rmul.append(-1*num)
        else:
            rmul.append(-1*num+1)

    else:

        num = 0
        while R > L:
            L *= 4
            num += 1

        rmul.append(num)

        if R==L:
            lmul.append(-1*num)
        else:
            lmul.append(-1*num+1)

rmul.append(0)

#print (lmul,rmul)
#for i in range(N+1):
#    print (want(i))

l = -1
r = N+2

while r-l > 2:

    m1 = (l*2+r)//3
    m2 = (l+r*2)//3

    r1 = want(m1)
    r2 = want(m2)

    if r1 < r2:
        r = m2
    else:
        l = m1

ans = float("inf")
for i in range(l-3,r+3):

    if i < 0 or i > N+1:
        continue
    ans = min(ans , want(i))

print (ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


def calc_mul4_dp(n, aaa):
    # result[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    # 第2項は巨大になり得るが、A_iの最大値 10^9 を超えたら常に末尾までが支配区間となるので、適当に上限でclip
    stack = [(10 ** 11, 10 ** 11, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 10
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    # aaa = [1, 10 ** 9] * (n // 2)
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    # print(aaa)
    print(solve(n, aaa))


# test()

n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
import numpy as np


def calc_mul4_dp(n, aaa):
    # result[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    # 第2項は巨大になり得るが、A_iの最大値 10^9 を超えたら常に末尾までが支配区間となるので、適当に上限でclip
    stack = [(10 ** 10, 10 ** 10, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 9
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    # aaa = [1, 10 ** 9] * (n // 2)
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    # print(aaa)
    print(solve(n, aaa))


# test()

n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
import numpy as np


def calc_mul4_dp(n, aaa):
    # result[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    # 第2項は巨大になり得るが、A_iの最大値 10^9/4 を超えたら常に末尾までが支配区間となるので、適当に上限でclip
    stack = [(10 ** 9, 10 ** 9, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 9 // 4
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    # aaa = [1, 10 ** 9] * (n // 2)
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    # print(aaa)
    print(solve(n, aaa))


# test()

n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
import numpy as np


def calc_mul4_dp(n, aaa):
    # dp[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    stack = [(10 ** 100, n), (aaa[-1], n - 1)]
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][1] - j)
            c = b
        stack.append((a, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    aaa = [1, 10 ** 9] * (n // 2)
    print(n)
    # print(aaa)
    print(solve(n, aaa))


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
import numpy as np


def calc_mul4_dp(n, aaa):
    # dp[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    stack = [(10 ** 18, n), (aaa[-1], n - 1)]
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][1] - j)
            c = b
        stack.append((a, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    aaa = [1, 10 ** 9] * (n // 2)
    print(n)
    # print(aaa)
    print(solve(n, aaa))


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
from math import ceil, log


def check(m, aaa):
    result = m
    curr = 0
    for a in aaa[m:]:
        while a < curr:
            a *= 4
            result += 2
        curr = a
    if m == 0:
        return result
    curr = 0
    for a in aaa[m - 1::-1]:
        while a < curr:
            a *= 4
            result += 2
        curr = a
    return result


n = int(input())
aaa = list(map(int, input().split()))
l, r = -1, n - 1
while l + 1 < r:
    m1 = (l + r) // 2
    m2 = m1 + 1
    res1 = check(m1, aaa)
    res2 = check(m2, aaa)
    # print(l, r, m1, m2, res1, res2)
    if res1 <= res2:
        r = m1
    else:
        l = m1
print(check(r, aaa))

Submission status: Wrong Answer

Solution code:
from math import ceil, log


def check(m, lll):
    result = m
    curr = 0
    for l in lll[m:]:
        if curr > l + 1e-7:
            mul = ceil(curr - l)
            mul += mul & 1
            result += mul
            curr = l + mul
        else:
            curr = l
    if m == 0:
        return result
    curr = 0
    for l in lll[m - 1::-1]:
        if curr > l + 1e-7:
            mul = ceil(curr - l)
            mul += mul & 1
            result += mul
            curr = l + mul
        else:
            curr = l
    return result


n = int(input())
aaa = list(map(int, input().split()))
lll = [log(a, 2) for a in aaa]
l, r = -1, n - 1
while l + 1 < r:
    m1 = (l + r) // 2
    m2 = m1 + 1
    res1 = check(m1, lll)
    res2 = check(m2, lll)
    # print(l, r, m1, m2, res1, res2)
    if res1 <= res2:
        r = m1
    else:
        l = m1
print(check(r, lll))

Submission status: Wrong Answer

Solution code:
from math import log2, ceil


def check(m, lll):
    result = m
    curr = 0
    for l in lll[m:]:
        if curr > l + 1e-7:
            mul = ceil(curr - l)
            if mul % 2 == 1:
                mul += 1
            result += mul
            curr = l + mul
        else:
            curr = l
    curr = 0
    for l in lll[m - 1::-1]:
        if curr > l + 1e-7:
            mul = ceil(curr - l)
            if mul % 2 == 1:
                mul += 1
            result += mul
            curr = l + mul
        else:
            curr = l
    return result


n = int(input())
aaa = list(map(int, input().split()))
lll = list(map(log2, aaa))
l, r = -1, n - 1
while l + 1 < r:
    m1 = (l + r) // 2
    m2 = m1 + 1
    res1 = check(m1, lll)
    res2 = check(m2, lll)
    # print(l, r, m1, m2, res1, res2)
    if res1 <= res2:
        r = m1
    else:
        l = m1
print(check(r, lll))

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
l,r=0,n+1
def g(x):
    c=1
    while x//4!=0:
        x=(x-x%4)//4
        c+=1
    return c
def f(x):
    c=x
    p=0
    if x>1:
        for i in range(x-2,-1,-1):
            if i!=n-1:
                if a[i+1]>a[i]:
                    p+=g(a[i+1]//a[i]+1)*2
            c+=p
    if x<n:
        p=0
        for i in range(x,n-1):
            if a[i+1]<a[i]:
                p+=g(a[i+1]//a[i]+1)*2
            c+=p
    return c
while r-l>2:
    s=(2*l+r)//3
    t=(l+2*r)//3
    if f(s)>f(t):
        l=s
    else:
        r=t
print(min(f(l),f(r),f(r-1)))

Submission status: Wrong Answer

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

def f(a, b):
    return (1+(-(-a//b)-1).bit_length())//2

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

dpr = [0]*N
Ar = A[:]
cnt = 0
for i in range(1, N):
    res = 0
    idx = i-1
    while cnt <= idx:
        k = f(Ar[idx+1], Ar[idx])
        if k:
            Ar[idx] *= 4**k
            res += k
        idx -= 1
        if not k:
            break
    else:
        dpr[i] += cnt
    dpr[i] += dpr[i-1] + res
    while cnt < i:
        if Ar[cnt] < Ar[cnt+1]*4:
            cnt += 1
        else:
            break

dpl = [0]*N
Al = A[:]
cnt = N-1
for i in range(N-2, -1, -1):
    res = 0
    idx = i+1
    while cnt >= idx:
        k = f(Al[idx-1], Al[idx])
        if k:
            Al[idx] *= 4**k
            res += k
        idx += 1
        if not k:
            break
    else:
        dpl[i] += N-1-cnt
    dpl[i] += dpl[i+1] + res
    while cnt > i:
        if Al[cnt] < Al[cnt-1]*4:
            cnt -= 1
        else:
            break
dpl = [2*dpl[i] for i in range(N)]
dpr = [0] + [i+1+2*dpr[i] for i in range(N)]
inf = 10**20
ans = inf
for i in range(N):
    ans = min(ans, dpr[i] + dpl[i])
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log,ceil
N=int(input())
A=list(map(int,input().split()))
inf=float("inf")
p=[0]*(N+1)
n=[0]*(N+1)
Stack_p=[(-inf,N-1)]
Stack_n=[(-inf,0)]
for i in range(N-1)[::-1]:
  k=ceil(log(A[i]/A[i+1],4))
  p[i]=p[i+1]
  t=i
  if k>=1:
    while k>0:
      #print(Stack_p,k,t,p)
      s,m=Stack_p.pop()
      p[i]+=k*(m-t)
      if k+s>=0:
        k+=s
        t=m
      else:
        k=0
        Stack_p.append((k+s,m))       
  elif k<0:
    Stack_p.append((k,i))
for i in range(2,N+1):
  k=ceil(log(A[i-1]/A[i-2],4))
  n[i]=n[i-1]
  t=i-1
  if k>=1:
    while k>0:
      #print(Stack_n,k,t)
      s,m=Stack_n.pop()
      n[i]+=k*(t-m)
      t=m
      if k+s>=0:
        k+=s
      else:
        k=0
        Stack_n.append((k+s,m))       
  elif k<0:
    Stack_n.append((k,i-1))
#print(p)
#print(n)
ans=inf
for i in range(N+1):
  ans=min(ans,i+2*n[i]+2*p[i])
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log,ceil
N=int(input())
A=list(map(int,input().split()))
inf=float("inf")
p=[0]*(N+1)
n=[0]*(N+1)
Stack_p=[(-inf,N-1)]
Stack_n=[(-inf,0)]
for i in range(N-1)[::-1]:
  k=ceil(log(A[i]/A[i+1],4))
  p[i]=p[i+1]
  t=i
  if k>=1:
    while k>0:
      s,m=Stack_p.pop()
      p[i]+=k*(m-t)
      if k+s>=0:
        k+=s
      else:
        k=0
        Stack_p.append((k+s,m))       
  elif k<0:
    Stack_p.append((k,i))
for i in range(2,N+1):
  k=ceil(log(A[i-1]/A[i-2],4))
  n[i]=n[i-1]
  t=i-1
  if k>=1:
    while k>0:
      #print(Stack_n,k)
      s,m=Stack_n.pop()
      n[i]+=k*(t-m)
      if k+s>=0:
        k+=s
      else:
        k=0
        Stack_n.append((k+s,m))       
  elif k<0:
    Stack_n.append((k,i-1))
#print(p)
#print(n)
ans=inf
for i in range(N+1):
  ans=min(ans,i+2*n[i]+2*p[i])
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log,ceil
N=int(input())
A=list(map(int,input().split()))
inf=float("inf")
p=[0]*(N+1)
n=[0]*(N+1)
Stack_p=[(-inf,N-1)]
Stack_n=[(-inf,0)]
for i in range(N-1)[::-1]:
  k=ceil(log(A[i]/A[i+1],4))
  p[i]=p[i+1]
  t=i
  if k>=1:
    while k>0:
      s,m=Stack_p.pop()
      p[i]+=k*(m-t)
      if k+s>=0:
        k+=s
      else:
        k=0
        Stack_p.append((k+s,m))       
  elif k<0:
    Stack_p.append((k,i))
for i in range(2,N+1):
  k=ceil(log(A[i-1]/A[i-2],4))
  n[i]=n[i-1]
  t=i-1
  if k>=1:
    while k>0:
      print(Stack_n,k)
      s,m=Stack_n.pop()
      n[i]+=k*(t-m)
      if k+s>=0:
        k+=s
      else:
        k=0
        Stack_n.append((k+s,m))       
  elif k<0:
    Stack_n.append((k,i-1))
#print(p)
#print(n)
ans=inf
for i in range(N+1):
  ans=min(ans,i+2*n[i]+2*p[i])
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log,ceil
N=int(input())
A=list(map(int,input().split()))
inf=float("inf")
ans=0
p=[0]*(N+1)
n=[0]*(N+1)
Stack_p=[(-inf,N-1)]
Stack_n=[(-inf,0)]
for i in range(N-1)[::-1]:
  k=ceil(log(A[i]/A[i+1],4))
  p[i]=p[i+1]
  t=i
  if k>=1:
    while k>0:
      s,m=Stack_p.pop()
      p[i]+=k*(m-t)
      if k+s>=0:
        k+=s
      else:
        k=0
        Stack_p.append((k+s,m))       
  elif k<0:
    Stack_p.append((k,i))
for i in range(2,N+1):
  k=ceil(log(A[i-1]/A[i-2],4))
  n[i]=n[i-1]
  t=i-1
  if k>=1:
    while k>0:
      s,m=Stack_n.pop()
      n[i]+=k*(t-m)
      if k+s>=0:
        k+=s
      else:
        k=0
        Stack_n.append((k+s,m))       
  elif k<0:
    Stack_n.append((k,i))
#print(p)
#print(n)
ans=inf
for i in range(N+1):
  ans=min(ans,i+2*n[i]+2*p[i])
print(ans)