Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)] 
          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s = s-set([now])
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        #try:
           # nxt = fl.index(-1)
        #except:
            #nxt = 0
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()

    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)]

          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s.discard(now)
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        #try:
            #nxt = fl.index(-1)
        #except:
            #nxt = 0
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()


    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

def resolve():
    N=int(input())
    A=list(map(int,input().split()))
    cnt=[0]*N
    for i in range(N):
        for j in range(N):
            if abs(A[i]-A[j])<=1:
                cnt[i]+=1
    print(max(cnt))




resolve()


### FIXED CODE ###

from collections import Counter, deque
# from copy import copy, deepcopy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    N=int(input())
    A=list(map(int,input().split()))
    AA=Counter(A)
    maxval=0
    for i in AA.keys():
        maxval=max(AA[i-1]+AA[i]+AA[i+1],maxval)

    print(maxval)



resolve()
### BUGGY CODE ###

from collections import deque
def dist(A,B):
    return abs(A[0]-B[0])+abs(A[1]-B[1])

N=int(input())
P=[0]*N

for i in range(N):
    x,y=map(int,input().split())
    P[i]=(x,y)

P=list(set(P))
N=len(P)
X=set(range(N))

S=[0]*N
D=[]
for k in range(N):
    if S[k]==0:
        S[k]=1
        Old_Old_=0
        Old_I=-1
        I=k
        Flag=False
        Y=set()
        while True:
            M=-1
            Old_Old_I=Old_I
            Old_I=I
            for i in X:
                if M<dist(P[I],P[i]):
                    J=i
                    M=dist(P[I],P[i])

            if J==Old_Old_I and Flag:
                break
            I=J
            S[I]=1
            Flag=True

        X-=Y
        D.append(dist(P[Old_I],P[J]))

print(max(D))

### FIXED CODE ###

N=int(input())
Z=[0]*N
W=[0]*N

for i in range(N):
    x,y=map(int,input().split())
    Z[i]=x+y
    W[i]=x-y

alpha=max(Z)-min(Z)
beta=max(W)-min(W)
print(max(alpha,beta))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

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

A = [[0]*n for _ in range(n)]

for i in range(n):
    if i != n-1:
        A[i][i] = 1
        A[i][i+1] = 1
    else:
        A[i][i] = 1
        A[i][0] = 1

X = [[0]*n for _ in range(n)]
for i in range(n):
    X[i][i] = 1

def Inv(A):
    """逆行列をnumpyを使わず求める"""
    
    #まずAを上三角行列にする。
    for p in range(len(A)):
        pivot = A[p][p]
        for j in range(p+1, len(A)):
            coef = A[j][p] / pivot
            A[j] = [aj-ap*coef for aj,ap in zip(A[j],A[p])]
            X[j] = [xj-xp*coef for xj,xp in zip(X[j],X[p])]

    #対角成分を1にする。
    for i in range(len(A)):
        X[i] = [xi/A[i][i] for xi in X[i]]
        A[i] = [ai/A[i][i] for ai in A[i]]

    #答えを出す。
    for i in range(len(A)-1,0,-1):
        for j in range(i):
            X[j] = [xj-xi*A[j][i] for xj,xi in zip(X[j],X[i])]
            A[j][i] = 0
    return X

InvA = Inv(A)

ans = [0]*n

for i in range(len(A)):
    ans[i] = int(sum([a*b for a,b in zip(InvA[i], B)])) * 2
    
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))
#n, m = map(int, input().split())
#s = input()
#s,t = input().split()
#
#readline = sys.stdin.readline
#n,m = [int(i) for i in readline().split()]
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

x2 = 0
for i in range(n):
    if i%2:
        x2 -= a[i]
    else:
        x2 += a[i]

ans = [0]*n
ans[0] = x2//2

for i in range(n-1):
    ans[i+1] = a[i] - ans[i]
    
for i in range(n):
    ans[i] *= 2
    
print(*ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

balls = Counter(A)
for i in range(N):
    # 除外
    balls[A[i]] -= 1

    # 2個以上のペア
    s = 0
    for k, v in balls.most_common():        
        if v >= 2:
            s += v * (v - 1) // 2
    print(s)
    balls[A[i]] += 1

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

balls = Counter(A)
s = 0
for k, v in balls.most_common():        
    if v >= 2:
        s += v * (v - 1) // 2

for i in range(N):
    c = balls[A[i]]
    d = (c * (c - 1) / 2) - ((c - 1) * (c - 2) / 2)
    print(int(s-d))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

N = int(input())
a = list(map(int, input().split()))
one = a.count(1)
two = a.count(2)
three = a.count(3)
dp = [[[-1 for i in range(N+1)] for j in range(N+1)] for k in range(N+1)]

def rec(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0
    if i > 0:
        res += rec(i-1, j, k) * i
    if j > 0:
        res += rec(i+1, j-1, k) * j
    if k > 0:
        res += rec(i, j+1, k-1) * k
    res += N
    res /= i+j+k
    dp[i][j][k] = res
    return res

rec(one, two, three)
print(dp[one][two][three])


### FIXED CODE ###

import sys
from collections import Counter
sys.setrecursionlimit(10000)

N = int(input())
a = list(map(int, input().split()))
dp = [[[-1 for i in range(N+1)] for j in range(N+1)] for k in range(N+1)]

def rec(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0
    if i > 0:
        res += rec(i-1, j, k) * i
    if j > 0:
        res += rec(i+1, j-1, k) * j
    if k > 0:
        res += rec(i, j+1, k-1) * k
    res += N
    res *= 1.0/(i+j+k)

    dp[i][j][k] = res
    return res

c = Counter(a)
one, two, three = c[1], c[2], c[3]
print(rec(one, two, three))
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [float('inf') for i in range(N)]
dp[0] = 0
for i in range(N-1):
  for j in range(1,K+1):
    if i < N-j:
      dp[i+j] = min(dp[i+j],dp[i] + abs(h[i+j]-h[i]))
print(dp[N-1])

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = np.array(A)
ans = np.array([float('inf')]*N)
ans[0] = 0
K = min(N-1,K)
for i in range(1,K+1):
  ans[i] = abs(A[0]-A[i])
for i in range(K+1,N):
  ans[i] = min(ans[i],np.min(ans[i-K:i]+np.abs(A[i]-A[i-K:i])))
print(int(ans[N-1]))
### BUGGY CODE ###

a, b, k = list(map(int, input().split()))
l = [i for i in range(a, b + 1) if (i < a + k) or (i > b - k)]
for i in l:
    print(i)


### FIXED CODE ###

a, b, k = list(map(int, input().split()))
a_l = [i for i in range(a, a + k) if i <= b]
b_l = [i for i in range(b - k+1, b+1) if i >= a]
for i in b_l:
    a_l.append(i)
ans = sorted(list(set(a_l)))
for i in ans:
    print(i)
### BUGGY CODE ###

import collections
import sys
N = int(input())
S = [input() for _ in range(N)]

c = collections.Counter(S)
ans = []

for i in range(len(c.most_common())):
    if i == 0:
        ans.append(((c.most_common()[0][0])))
    
    if i != 0:
        if (c.most_common()[i-1][1]) == (c.most_common()[i][1]):
            
            ans.append(((c.most_common()[i][0])))
        else:
            break

ans.sort()
 
for i in ans:
    print(i)

### FIXED CODE ###

import collections
import sys
N = int(input())
S = [input() for _ in range(N)]

c = collections.Counter(S)
ans = []
li=c.most_common()
for i in range(len(li)):
    if i == 0:
        ans.append(((li[0][0])))
    
    if i != 0:
        if (li[i-1][1]) == (li[i][1]):
            
            ans.append(((li[i][0])))
        else:
            break

ans.sort()

for i in ans:
    print(i)
### BUGGY CODE ###

N = int(input())
P = [int(x) for x in input().split()]
ans = 0
for i in range(N):
    for j in range(i,-1,-1):
        if P[i] > P[j]:
            break
    else:
        ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
P = [int(x) for x in input().split()]
mins = [0]*N
mins[0] = P[0]
for n in range(1,N):
    mins[n] = min(P[n],mins[n-1])
ans = 0
for i in range(N):
    if P[i] == mins[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K, Q = MAP()
A = LIST()

ans = INF
# 使う要素の最小値とする値xを全探索
for x in A:
    # 数列Aをx未満の値で区切った数列Bを作る
    B = []
    tmp = []
    for i in range(N):
        if A[i] >= x:
            tmp.append(A[i])
        else:
            B.append(tmp)
            tmp = []
    B.append(tmp)
    # 数列B内の各数列から、使える要素を集める
    C =  []
    for li in B:
        m = len(li)
        li.sort()
        C += li[:max(m-K+1, 0)]
    # 集めた要素からQ個をクエリで使うので、小さい方からQ番目が使う要素の最大値y
    C.sort()
    if len(C) < Q:
        continue
    y = C[Q-1]
    ans = min(ans, y - x)
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K, Q = MAP()
A = LIST()

ans = INF
# 使う要素の最小値とする値xを全探索
for x in A:
    # 数列Aをx未満の値で区切った数列Bを作る
    B = []
    tmp = []
    for i in range(N):
        if A[i] >= x:
            tmp.append(A[i])
        else:
            B.append(tmp)
            tmp = []
    B.append(tmp)
    # 数列B内の各数列から、使える要素を集める
    C =  []
    for li in B:
        m = len(li)
        li.sort()
        C += li[:max(m-K+1, 0)]
    # 集めた要素からQ個をクエリで使うので、小さい方からQ番目が使う要素の最大値y
    C.sort()
    if len(C) < Q:
        continue
    y = C[Q-1]
    ans = min(ans, y - x)
print(ans)
### BUGGY CODE ###

import math
num_limit = int(input())
s_limit_1 = int(num_limit**0.5)
s_limit_2 = int((num_limit/2)**0.5)
s_limit_3 = int((num_limit/3)**0.5)
for i in range(1,num_limit+1):
    xyz_list = []
    xyz_count = 0
    s_limit_1 = int(i ** 0.5)
    j = 0
    k = 0
    l = 0
    for j in range(1,s_limit_1+1):
        for k in range(1,j+1):
            for l in range(1,k+1):
                if i == j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    if j == k and k == l:
                        xyz_count += 1
                    elif j == k and k > l or j > k and k == l:
                        xyz_count += 3
                    else:
                        xyz_count += 6
                if i < j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    break
    print(xyz_count)

### FIXED CODE ###

num_limit = int(input())
num_list = [0] * num_limit
j_limit = int(num_limit ** 0.5)
for j in range(1,j_limit+1):
    for k in range(1,j + 1):
        for l in range(1,k+1):
            if num_limit >= j**2 + k**2 + l**2 + j*k + k*l + l*j:
                if j > k:
                    if k > l:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 6
                    else:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                elif k > l:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                else:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 1
for i in num_list:
    print(i)
### BUGGY CODE ###

from itertools import combinations

N = int(input())
S = [input() for _ in range(N)]

ans = 0
for s in combinations(S, 3):
    _flag = True
    pre = list(map(lambda x: x[0], s))
    for p in pre:
        if p not in ['M', 'A', 'R', 'C', 'H']:
            _flag = False
    if len(pre) != len(list(set(pre))):
        _flag = False
    if _flag:
        ans += 1
print(ans)


### FIXED CODE ###

from itertools import combinations
from collections import Counter

N = int(input())
S = Counter()
for _ in range(N):
    S[input()[0]] += 1
print(sum([S[a]*S[b]*S[c] for a, b, c in combinations('MARCH', 3)]))
### BUGGY CODE ###

n= int(input())
a=list(map(int,input().split()))
ans=1
for i in range(n):
    ans=ans*a[i]
if ans<=(10**18):
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n= int(input())
a=list(map(int,input().split()))
a.sort()
ans=1
for i in a:
    ans=ans*i
    if ans>(10**18):
        print(-1)
        break
    elif ans==0:
        print(ans)
        break
if ans<=(10**18)and ans!=0:
    print(ans)
### BUGGY CODE ###

s = input()
k = int(input())

n = len(s)

d = [set() for i in range(26)]

for i in range(n):
    for j in range(i+1, n+1):
        tmp = s[i:j]
        d[ord(tmp[0]) - 97].add(tmp)

for i in range(26):
    num = i
    if len(d[i]) >= k:
        break
    else:
        k -= len(d[i])

a = sorted(list(d[num]))
print(a[k-1])



### FIXED CODE ###

s = input()
k = int(input())

n = len(s)

d = set()
for i in range(n):
    for j in range(i+1, min(i+k+1,n+1)):
        tmp = s[i:j]
        d.add(tmp)
a = sorted(list(d))
print(a[k-1])
### BUGGY CODE ###

import heapq
H,W = map(int, input().split())

A = []
queue = []
inf = float('inf')
for i in range(H):
    A.append([0 if c == '#' else inf for c in input()])
    for j in range(W):
        if A[i][j] == 0:
            heapq.heappush(queue, [0, [i,j]])

mx = 0
dx = [[0,1], [1,0], [-1,0], [0,-1]]
n = len(queue)
for _ in range(n):
    score, p = heapq.heappop(queue)
    for x,y in dx:
        if p[1]+x>=W or p[1]+x<0 or p[0]+y>=H or p[0]+y<0:
            continue
        A[p[0]+y][p[1]+x] = score+1
        heapq.heappush(queue, [score+1, [p[0]+y, p[1]+x]])
        mx = max(score+1, mx)

while queue:
    score, p = heapq.heappop(queue)
    if score > A[p[0]][p[1]]:
        continue
    for x,y in dx:
        if p[1]+x>=W or p[1]+x<0 or p[0]+y>=H or p[0]+y<0:
            continue
        if A[p[0]+y][p[1]+x] > score+1:
            A[p[0]+y][p[1]+x] = score+1
            heapq.heappush(queue, [score+1, [p[0]+y, p[1]+x]])
            mx = max(score + 1, mx)
print(mx)

### FIXED CODE ###

from collections import deque

def bfs(grid, queue, wall):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        cnt,y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([cnt+1,y_,x_])
            grid[y_][x_] = wall
            ans = max(ans, cnt+1)
    return ans

H,W = map(int, input().split())
wall = '#'
queue = deque([])
edges = [wall for i in range(W+2)]
grid = [edges]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([0,i,j])
    grid.append(S)
grid.append(edges)
print(bfs(grid, queue, wall))
### BUGGY CODE ###

N, M, K = map(int, input().split())

friends = [set() for _ in range(N)]
for _ in range(M):
    a,b = map(lambda x: int(x)-1, input().split())
    friends[a].add(b)
    friends[b].add(a)

blocks = [set() for _ in range(N)]
for _ in range(K):
    c,d = map(lambda x: int(x)-1, input().split())
    blocks[c].add(d)
    blocks[d].add(c)

ans = [0]*N
visited = [False]*N
for i in range(N):
    if visited[i]: 
        continue
    d = [i]
    check = {i} 
    while len(d):
        tmp = d.pop()
        for k in friends[tmp]:
            if visited[k]:
                continue
            d.append(k) 
        visited[tmp] = True
        check.add(tmp)
    for j in check:
        ans[j] += len(check) - len(friends[j]&check) - len(blocks[j]&check) - 1
print(*ans)


### FIXED CODE ###

N, M, K = map(int, input().split())

friends = [set() for _ in range(N)]
for _ in range(M):
    a,b = map(lambda x: int(x)-1, input().split())
    friends[a].add(b)
    friends[b].add(a)

blocks = [set() for _ in range(N)]
for _ in range(K):
    c,d = map(lambda x: int(x)-1, input().split())
    blocks[c].add(d)
    blocks[d].add(c)

ans = [0]*N
visited = [False]*N
for i in range(N):
    if visited[i]:
        continue
    visited[i] = True
    d = [i]
    check = {i} 
    while len(d):
        tmp = d.pop()
        for k in friends[tmp]:
            if visited[k]:
                continue
            d.append(k)
            visited[k] = True
            check.add(k)
    for j in check:
        ans[j] += len(check) - len(friends[j]&check) - len(blocks[j]&check) - 1
print(*ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

MAX_N = 100010
memo = [-1] * MAX_N

def f(n, a_list):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        for a in a_list:
            if N - a == 1:
                return 1
        return 2
    # すでに探索済みならメモを参照する
    elif memo[n] != -1:
        return memo[n]
    else:
        is_next_damaged = False
        is_2next_damaged = False
        for a in a_list:
            if N - a == n-1:
                is_next_damaged = True
            if N - a == n-2:
                is_2next_damaged = True
        if is_next_damaged == True and is_2next_damaged == False:
            res = f(n-2, a_list)
        if is_next_damaged == False and is_2next_damaged == True:
            res = f(n-1, a_list)
        if is_next_damaged == False and is_2next_damaged == False:
            res = f(n-1, a_list) + f(n-2, a_list)

    # メモ
    memo[n] = res
    return res

if __name__ == '__main__':
    N, M = map(int, input().split())
    a_list = [int(input()) for i in range(M)]

    divided_by = 1000000007

    answer = -1

    # まず移動方法がない場合を考える。
    min_diff = sys.maxsize
    for i in range(1, len(a_list)):
        min_diff = min(min_diff, a_list[i] - a_list[i - 1])

    if min_diff == 1:
        answer = 0
    else:
        # 何らかなの移動方法が必ず存在する場合
        answer = f(N, a_list)%divided_by

    print(answer)


### FIXED CODE ###

if __name__ == '__main__':
   n, m = map(int,input().split())
   a = set([int(input()) for i in range(m)])

   MOD = 1000000007

   dp = [0 for i in range(n+1)]
   dp[0] = 1
   if 1 in a:
      dp[1] = 0
   else:
      dp[1] = 1

   for i in range(2,n+1):
      if (i-1 in a) and (i-2 in a):
         dp[i] = 0
      elif i-1 in a:
         dp[i] = dp[i-2] % MOD
      elif i-2 in a:
         dp[i] = dp[i-1] % MOD
      else:
         dp[i] = (dp[i-1] + dp[i-2]) % MOD

   print(dp[n])
### BUGGY CODE ###

from math import log, ceil


def create_dp_table(aaa):
    dp = [list(range(16)) for _ in range(n)]
    for i, (pa, a, dpp, dpi) in enumerate(zip(aaa, aaa[1:], dp, dp[1:])):
        ds = ceil(log(a / pa, 4))
        for j in range(16):
            k = j + ds
            if k < 16:
                dpi[j] += dpp[max(0, k)]
            else:
                dpi[j] += dpp[15] + (k - 15) * (i + 1)
    return dp


def search_min(neg, pos):
    ret = min(n + neg[-1][0] * 2, pos[0][0] * 2)
    for i in range(1, n):
        ret = min(ret, i + neg[i - 1][0] * 2 + pos[i][0] * 2)
    return ret


n = int(input())
aaa = list(map(int, input().split()))
neg = create_dp_table(aaa)
pos = create_dp_table(list(reversed(aaa)))
pos.reverse()
print(search_min(neg, pos))


### FIXED CODE ###

import numpy as np


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

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    stack = [(10 ** 20, 10 ** 20, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 19
    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))