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

from bisect import bisect_left, bisect_right
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    s = [0]*n
    l, r = -1*10**18, 10**18
    while l+1 < r:
        p = (l+r)//2
        for i in range(n):
            sl, sr = -1, n
            if a[i] < 0:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sr = sp
                    else:
                        sl = sp
                s[i] = n-sr
            else:
                while sl+1 < sr:
                    sp = (sl+sr)//2
                    if a[sp]*a[i] < p:
                        sl = sp
                    else:
                        sr = sp
                s[i] = sr
            if a[i]**2 < p:
                s[i] -= 1
        if sum(s)//2 < k:
            l = p
        else:
            r = p
    print(l)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt_neg, cnt_zro, cnt_pos = 0, 0, 0
    neg_a, zro_a, pos_a = [], [], []
    n_ap = neg_a.append
    z_ap = zro_a.append
    p_ap = pos_a.append
    for v in a:
        if v < 0:
            cnt_neg += 1
            n_ap(v)
        elif v == 0:
            cnt_zro += 1
            z_ap(v)
        else:
            cnt_pos += 1
            p_ap(v)
    num_neg_pair = cnt_neg * cnt_pos
    num_pos_pair = cnt_neg*(cnt_neg-1)//2 + cnt_pos*(cnt_pos-1)//2
    num_zro_pair = n*(n-1)//2 - num_neg_pair - num_pos_pair
    if k <= num_neg_pair:
        neg_a = np.array(neg_a)
        pos_a = np.array(pos_a)
        l = -1*10**18
        r = 0
        while l+1 < r:
            p = (l+r)//2
            cnt = np.searchsorted(pos_a, p//neg_a, side="riget").sum()
            result = n*cnt_neg - (cnt + (cnt_neg + cnt_zro)*cnt_neg)
            if result < k:
                l = p
            else:
                r = p
        print(l)
    elif k <= num_neg_pair + num_zro_pair:
        print("0")
    else:
        k -= num_neg_pair + num_zro_pair
        for i in range(len(neg_a)):
            neg_a[i] = -neg_a[i]
        neg_a = np.array(neg_a)
        neg_a = np.sort(neg_a)
        pos_a = np.array(pos_a)
        l = 1
        r = 10**18+1
        while l+1 < r:
            p = (l+r)//2
            cnt_1 = np.searchsorted(neg_a, (p+neg_a-1)//neg_a, side="left").sum()
            cnt_2 = np.searchsorted(pos_a, (p+pos_a-1)//pos_a, side="left").sum()
            cnt_1 -= np.count_nonzero(neg_a < (p+neg_a-1)//neg_a)
            cnt_2 -= np.count_nonzero(pos_a < (p+pos_a-1)//pos_a)
            result = (cnt_1 + cnt_2)//2
            if result < k:
                l = p
            else:
                r = p
        print(l)

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

n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
b = []
for _ in range(q):
    b.append([int(i) for i in input().split()])


for i in range(q):
    for j in range(n):
        if a[j] == b[i][0]:
            a[j] = b[i][1]
    print(sum(a))



### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]


q = int(input())
b = []
for _ in range(q):
    b.append([int(i) for i in input().split()])

al = {}
suma = sum(a)

for i in a:
    if i not in al:
        al[i] = 1
    else:
        al[i] += 1

for i in range(q):
    if b[i][0] in al:
        suma += (b[i][1] - b[i][0]) * al[b[i][0]]
        
        if b[i][1] in al:
            
            al[b[i][1]] += al[b[i][0]]
            al[b[i][0]] = 0
        else:
            al[b[i][1]] = al[b[i][0]]
            al[b[i][0]] = 0
    print(suma)
### BUGGY CODE ###

M=10**9+7
mod =M
import sys
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

from collections import defaultdict
N=input()
xs = map(int, input().split())
ys = []
d = defaultdict(int)
for x in xs:
    ps = prime_decomposition(x)
    psd = defaultdict(int)
    for p, c in ps:
        psd[p] = c
        d[p] = max(d[p], c)
    ys.append(psd)
r = 0
for ps in ys:
    t = 1
    for p in d:
        t = t*p**(d[p]-ps[p])
    r = (r+t)
print(r%M)


### FIXED CODE ###

M=10**9+7
mod =M
import sys
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
NNN = (10**6)
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

from collections import defaultdict
N=input()
xs = list(map(int, input().split()))
ys = []
d = defaultdict(int)
for x in xs:
    ps = prime_decomposition(x)
    psd = defaultdict(int)
    for p, c in ps:
        psd[p] = c
        d[p] = max(d[p], c)
    ys.append(psd)
g=1
for p in d:
    g=mul(g,p**(d[p])%M)%M
r=0
for x in xs:
    r = (r+mul(g,inverse[x]))%M
print(r%M)
### BUGGY CODE ###

N,K,Q = map(int,input().split(" "))
score = [0]
for _ in range(N):
    score.append(K)

for _ in range(Q):
    ans = int(input())
    for i in range(1,N+1):
        if i != ans:
            score[i]-=1

for i in range(1,N+1):
    if score[i] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K,Q = map(int,input().split(" "))
score = [0]
for _ in range(N):
    score.append(K)

for _ in range(Q):
    ans = int(input())
    score[ans] +=1

for i in range(1,N+1):
    if score[i] > Q:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N, M = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
mat = [[0 for i in range(N)] for j in range(N)]
for j in range(M):
    a, b = [int(x) for x in input().split()]
    mat[a - 1][b - 1] = H[b - 1]
    mat[b - 1][a - 1] = H[a - 1]

count = 0
for i in range(N):
    h = H[i]
    max_h = max(mat[i])
    if h > max_h:
        count += 1
print(count)

### FIXED CODE ###

N, M = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
nodes = [1 for i in range(N)]
for j in range(M):
    a, b = [int(x) for x in input().split()]
    if H[a - 1] <= H[b - 1]:
        nodes[a - 1] = 0
    if H[b - 1] <= H[a - 1]:
        nodes[b - 1] = 0
print(sum(nodes))
### BUGGY CODE ###

n = int(input())
s = input()
ch = {}
for c in s:
  if c in ch:
    ch[c] += 1
  else:
    ch[c] = 1

ans = 1

for c in ch:
  if ch[c] != 0:
    ans *= 1 + ch[c]
  else:
    continue
  if ans >= 1000000007:
    ans -= 1000000007

ans += 1000000007
ans -= 1
while ans >= 1000000007:
  ans -= 1000000007
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ch = {}
for c in s:
  if c in ch:
    ch[c] += 1
  else:
    ch[c] = 1

ans = 1

for c in ch:
  ans *= 1 + ch[c]
  
  while ans >= 1000000007:
    ans -= 1000000007

ans += 1000000007
ans -= 1
while ans >= 1000000007:
  ans -= 1000000007

print(ans)
### BUGGY CODE ###

import sys
from itertools import accumulate
import bisect
import numpy as np
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
H,W = inputs()
meiro = [list(input()) for i in range(H)]
#print(meiro)
imosw = [[0]*(W) for _ in range(H)]
imosh = [[0]*(W) for _ in range(H)]
for i in range(H):
    cnt=0
    for j in range(W):
        if meiro[i][j]=="#":
            if cnt!=0:
                imosw[i][j]-=cnt
                imosw[i][j-cnt]+=cnt
            cnt = 0
        else:
            cnt+=1
    if cnt!=0:
    	imosw[i][W-1-cnt+1]+=cnt
for j in range(W):
    cnt= 0
    for i in range(H):
        if meiro[i][j]=="#":
            if cnt!=0:
                imosh[i][j]-=cnt
                imosh[i-cnt][j]+=cnt
            cnt = 0
        else:
            cnt+=1
    if cnt!=0:
    	imosh[H-1-cnt+1][j]+=cnt
imosw = np.cumsum(imosw, axis=1)
imosh = np.cumsum(imosh, axis=0)
ans = np.max(imosw+imosh)-1
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
meiro = [list(input()) for i in range(H)]
right = [[0 for _ in range(W)] for _ in range(H)]
left= [[0 for _ in range(W)] for _ in range(H)]
up = [[0 for _ in range(W)] for _ in range(H)]
down = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    cur=0
    for j in range(W):
        if meiro[i][j]=="#":
            cur = 0
        else:
            cur +=1
        left[i][j]=cur
for i in range(H):
    cur=0
    for j in range(W-1,-1,-1):
        if meiro[i][j]=="#":
            cur = 0
        else:
            cur +=1
        right[i][j]=cur
for i in range(W):
    cur=0
    for j in range(H):
        if meiro[j][i]=="#":
            cur = 0
        else:
            cur +=1
        up[j][i]=cur
for i in range(W):
    cur=0
    for j in range(H-1,-1,-1):
        if meiro[j][i]=="#":
            cur = 0
        else:
            cur +=1
        down[j][i]=cur
res = 0
for i in range(H):
    for j in range(W):
        res = max(res,right[i][j]+left[i][j]+up[i][j]+down[i][j]-3)
print(res)
### BUGGY CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n=int(input())

row,col,w=[],[],[]
for i in range(n-1):
  a,b,c=nii()
  row.append(a-1)
  col.append(b-1)
  w.append(c)

q,k=nii()
k-=1

g=csr_matrix((w,(row,col)),shape=(n,n))
d=dijkstra(g,indices=k,directed=False)

for i in range(q):
  x,y=nii()
  x-=1
  y-=1
  print(int(d[x]+d[y]))

### FIXED CODE ###

from collections import deque

n=int(input())

tree=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    tree[a].append([b,c])
    tree[b].append([a,c])

q,k=map(int,input().split())
k-=1

dist=[-1 for i in range(n)]
dist[k]=0
que=deque()
que.append(k)
while que:
    x=que.popleft()
    for p in tree[x]:
        if dist[p[0]]==-1:
            que.append(p[0])
            dist[p[0]]=dist[x]+p[1]
ans=[]
for i in range(q):
    x,y=map(int,input().split())
    x-=1;y-=1
    ans.append(dist[x]+dist[y])

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

s=input()

s2list=list(s.replace("BC","D"))
#print(s2list)

block_list=[]
bl=[]
for s2 in s2list:
  if s2=="A" or s2=="D":
    bl.append(s2)
  else:
    if len(bl)>0:
      block_list.append("".join(bl))
      bl=[]
else:
  if len(bl)>0:
    block_list.append("".join(bl))
#print(block_list)

answer=0
for bl in block_list:
  while(bl.find("AD")!=-1):
    answer+=bl.count("AD")
    bl=bl.replace("AD","DA")
    
print(answer)

### FIXED CODE ###

s=input()

s2list=list(s.replace("BC","D"))
#print(s2list)

block_list=[]
bl=[]
for s2 in s2list:
  if s2=="A" or s2=="D":
    bl.append(s2)
  else:
    if len(bl)>0:
      block_list.append("".join(bl))
      bl=[]
else:
  if len(bl)>0:
    block_list.append("".join(bl))
#print(block_list)

answer=0
for bl in block_list:
  #print(bl)
  cnt_a=0
  for c in bl:
    if c=="A":
      cnt_a+=1
    else:
      answer+=cnt_a
    
print(answer)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

for i in range(n):
    b = a[i]
    a.remove(b)
    print(max(a))
    a.insert(i,b)


### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

b = sorted(a)

for i in a:
    if i == b[-1]:
        print(b[-2])
    else:
        print(b[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import copy
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    for i in range(N):
        if i != A.index(max(A)):
            print(max(A))
            continue
        Ap = []
        Ap = copy.copy(A)
        del Ap[i]
        print(max(Ap))
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import copy
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    Am = max(A)
    if A.count(Am)>1:
        for j in range(N):
            print(Am)
        return
    Ap = copy.copy(A)
    set(Ap)
    Ap.sort(reverse=True)
    for i in range(N):
        if  A[i] != Am:
            print(Am)
        else:
            print(Ap[1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, Q = map(int, input().split())
AB = [None] * (N-1)
for i in range(N-1):
    a, b = map(int, input().split())
    AB[i] = (a, b)
PX = [None] * (Q)
for i in range(Q):
    p, x = map(int, input().split())
    PX[i] = (p, x)
    
edges = AB[:]
vals = PX[:]

from collections import defaultdict
vals_dict = defaultdict(lambda: 0)
for v, n in vals:
    vals_dict[v] += n
#print(vals_dict)

graph = defaultdict(lambda: {})
for a, b in edges:
    graph[a][b] = vals_dict[b]
    graph[b][a] = vals_dict[a]
#print(graph)
    

from heapq import heappush, heappop
def dijkstra(graph, start, N):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shortest = dijkstra(graph, 1, N)
shortest = [s+vals_dict[1] for s in shortest]
#print(shortest)
ans = ' '.join(map(str, shortest[1:]))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
AB = [None] * (N-1)
for i in range(N-1):
    a, b = map(int, input().split())
    AB[i] = (a, b)
PX = [None] * (Q)
for i in range(Q):
    p, x = map(int, input().split())
    PX[i] = (p, x)
    
edges = AB[:]
vals = PX[:]

from collections import defaultdict
vals_dict = defaultdict(lambda: 0)
for v, n in vals:
    vals_dict[v] += n
#print(vals_dict)

graph = defaultdict(lambda: {})
for a, b in edges:
    graph[a][b] = vals_dict[b]
    graph[b][a] = vals_dict[a]
#print(graph)
    

from heapq import heappush, heappop
def dijkstra(graph, start, N):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shortest = dijkstra(graph, 1, N)
shortest = [s+vals_dict[1] for s in shortest]
#print(shortest)
ans = ' '.join(map(str, shortest[1:]))
print(ans)
### BUGGY CODE ###

# 初期入力
import sys
input = sys.stdin.readline
N = int(input())

#約数リストを作る
ans =0
for n in range(1, N+1):
    for m in range(n, N+1, n):
        ans +=m

print(ans)

### FIXED CODE ###

#https://www.youtube.com/watch?v=3gFnZhZlAF8
#【競プロ実況】ABC172 AからD問題【かつっぱ】
# 等差数列の和
# 初期入力
import sys
input = sys.stdin.readline
N = int(input())
ans =0
for i in range(1,N+1):
    n =N//i #項数
    ans +=n*(2*i +(n-1)*i)//2
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
aa = np.array(A)
aa = np.sort(aa)
for i in range(len(aa)):
  div = []
  for j in range(i+1,len(aa)):
    if aa[j]%aa[i] == 0:
      div.append(j)
      if aa[j] == aa[i]:
        div.append(i)
  aa = np.delete(aa,div,0)
print(len(aa))

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
aa = sorted(A)
ans = [0 for i in range(aa[-1]+1)]
for i in aa:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2,aa[-1]+1,i):
      ans[j] += 2
print(ans.count(1))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
N, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [[0] * (C + 1) for _ in range(N)]
mod = 10 ** 9 + 7
for i in range(N):
  for j in range(C + 1):
    for k in range(a[i], b[i] + 1):
      c[i][j] += pow(k, j, mod)
dpx = [0] * (C + 1)
dpy = [0] * (C + 1)
dpx[0] = 1
for i in range(N):
  if i % 2:
    dpx = [0] * (C + 1)
  else:
    dpy = [0] * (C + 1)
  for j in range(C + 1):
    for k in range(j, C + 1):
      if i % 2:
        dpx[k] += dpy[j] * c[i][k - j]
        dpx[k] %= mod
      else:
        dpy[k] += dpx[j] * c[i][k - j]
        dpy[k] %= mod
if N % 2:
  print(dpy[-1] % mod)
else:
  print(dpx[-1] % mod)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
N, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0] * (N * (C + 1))
mod = 10 ** 9 + 7
for i in range(N):
  c[i * (C + 1)] = b[i] - a[i] + 1
for i in range(N):
  for k in range(a[i], b[i] + 1):
    t = 1
    for j in range(C):
      t *= k
      t %= mod 
      c[i * (C + 1) + j + 1] += t
      c[i * (C + 1) + j + 1] %= mod
dpx = [0] * (C + 1)
dpy = [0] * (C + 1)
dpx[0] = 1
for i in range(N):
  if i % 2:
    dpx = [0] * (C + 1)
  else:
    dpy = [0] * (C + 1)
  for j in range(C + 1):
    for k in range(j, C + 1):
      if i % 2:
        dpx[k] += dpy[j] * c[i * (C + 1) + k - j]
        dpx[k] %= mod
      else:
        dpy[k] += dpx[j] * c[i * (C + 1) + k - j]
        dpy[k] %= mod
if N % 2:
  print(dpy[-1] % mod)
else:
  print(dpx[-1] % mod)
### BUGGY CODE ###

# coding: utf-8

S = input()
Q = int(input())
# print("S:{}".format(S))
# print("Q:{}".format(Q))
query = []

for i in range(Q):
    query.append(input().split())


# for i in query:
#     print(i)

# for i in query:
#     if len(i) == 1:
#         S = S[::-1]
#     else:
#         if i[1]=="1":
#             S = i[2]+S
#         else:
#             S += i[2]
# print(S)
left = True
for i in query:
    if len(i) == 1:
        left = not left
        # print(left)
    else:
        if i[1]=="1":
            if left:
                S = i[2]+S
            else:
                S += i[2]
        else:
            if left:
                S += i[2]
            else:
                S = i[2]+S

print(S) if left else print(S[::-1])


### FIXED CODE ###

# coding: utf-8

S = input()
Q = int(input())

query = []

for i in range(Q):
    query.append(input().split())


bool = True
pre =''
suf =''

for i in query:
    if len(i) == 1:
        bool = not(bool)

    else:
        if i[1]=="1":
            if bool:
                pre = i[2]+pre
            else:
                suf += i[2]
        else:
            if bool:
                suf += i[2]
            else:
                pre = i[2]+pre

S = pre+ S +suf
print(S) if bool else print(S[::-1])
### BUGGY CODE ###

N = int(input())
S = [i for i in input()]

flg = 0
idx = 0
for i in S:
    if i == '#' and flg == 0:
        flg = 1
        break
    idx += 1

if flg == 1:
    a = S[idx+1:].count('.')
    b = S[idx:].count('#')
    if S[-1] == '#':
        for ct in range(1, N+1):
            if S[-ct] == '.':
                break
        b -= ct-1
    ans = min(a, b)
else:
    ans = 0
key = [0]
S = S[idx:]
for i in range(1, len(S)):
    if S[i] == '#' and S[i-1] == '.':
        key.append(i)
if len(key) > 2:
    for i in range(len(key)-1):
        c = S[:key[i+1]].count('#') + S[key[i+1]:].count('.')
        ans = min(ans, c)

print(ans)


### FIXED CODE ###

N = int(input())
S = [i for i in input()]

flg = 0
idx = 0
for i in S:
    if i == '#':
        flg = 1
        break
    idx += 1

if flg == 1:
    a = S[idx+1:].count('.')
    b = S[idx:].count('#')
    if S[-1] == '#':
        for ct in range(1, N+1):
            if S[-ct] == '.':
                break
        b -= ct-1
    ans = min(a, b)
else:
    ans = 0

count_blk = []
count_wht = []

ct_blk = 0
ct_wht = 0
for i in S:
    if i == '#':
        ct_blk += 1
    else:
        ct_wht += 1
    count_blk.append(ct_blk)
    count_wht.append(ct_wht)

for i in range(N):
    ans = min(ans, count_blk[i] + ct_wht - count_wht[i])

print(ans)
### BUGGY CODE ###

from math import log2, ceil


def _check(bbb):
    ret = 0
    pb = -1
    for b in bbb:
        if pb > b:
            d = ceil((pb - b) / 2) * 2
            ret += d
            b += d
        pb = b
    return ret


def check(x, bbb):
    ret = x
    ret += _check(bbb[x:])
    ret += _check(reversed(bbb[:x]))
    return ret


def solve(n, aaa):
    l = 0
    r = n
    bbb = list(map(log2, aaa))
    while l < r:
        m1 = (l + r) // 2
        m2 = m1 + 1
        res1 = check(m1, bbb)
        res2 = check(m2, bbb)
        # print(l, r, m1, m2, res1, res2)
        if res1 > res2:
            l = m1 + 1
        else:
            r = m1
    return check(r, bbb)


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


### 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))
### BUGGY CODE ###

from collections import deque
n=int(input())
a=list(map(int,input().split()))

sus=deque([sum(a)])
q=int(input())
for i in range(q):
  count=0
  b,c=map(int,input().split())
  for j in range(n):
    if a[j]==b:
      a[j]=c
      count+=1
  sus.append(sus[-1]+(c-b)*count)
  print(sus[-1])
#print(sus)

### FIXED CODE ###

n=int(input())
a=[0]*(10**5)
A=list(map(int,input().split()))
su=0
for i in range(n):
  su+=A[i]
  a[A[i]-1]+=1
q=int(input())
sus=[su]
for i in range(q):
  
  b,c=map(lambda x:int(x)-1,input().split())
  sus.append(sus[-1]+(c-b)*a[b])
  a[c]+=a[b]
  a[b]-=a[b]
  print(sus[-1])
### BUGGY CODE ###

n = int(input())
s = list(map(int,list(input())))

#L = [str(i).zfill(3) for i in range(1000)]
#def find_i(target,L):


ans_L = []
length = len(s)
count = 0

for i in range(1000):
    i = list(str(i).zfill(3))
    #print(i)
    idx = 0
    tmp_L = []

    for j in range(3):
        for k in range(idx,length):
            if str(i[j]) == str(s[k]):
                idx = k+1
                tmp_L.append(str(i[j]))
                break

    if len(tmp_L) == 3:
        ans_L.append("".join(tmp_L))

print(len(set(ans_L)))
#print(set(ans_L))

### FIXED CODE ###

n = int(input())
s = list(map(int,list(input())))


ans_L = []
length = len(s)
count = 0

for i in range(1000):
    i = list(str(i).zfill(3))
    idx = 0
    cnt = 0
    for j in range(3):
        for k in range(idx,length):
            if str(i[j]) == str(s[k]):
                idx = k+1
                cnt += 1
                break
        if cnt ==0:
            break

    #if len(tmp_L) == 3:
    #    ans_L.append("".join(tmp_L))
    if cnt == 3:
        count +=1

print(count)
#print(set(ans_L))