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

from collections import deque
def main():
  h,w=map(int,input().split())
  hw=h*w
  maze=[list(input()) for i in range(h)]
  visited=[[hw]*w for i in range(h)]
  ans,q=0,deque()
  for i in range(h):
    for j in range(w):
      if maze[i][j]=='#':
        q.append((i,j))
        visited[i][j]=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==hw:
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()


### FIXED CODE ###

from collections import deque
def main():
  h,w=map(int,input().split())
  hw=h*w
  maze=[list(input()) for i in range(h)]
  visited=[[hw]*w for i in range(h)]
  ans,q=0,deque()
  for i in range(h):
    for j in range(w):
      if maze[i][j]=='#':
        q.append((i,j))
        visited[i][j]=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==hw:
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

n, m = map(int, input().split())
A = list((map(int, input().split())))
for _ in range(m):
    A.sort()
    A[-1] = A[-1] // 2
print(sum(A))

### FIXED CODE ###

import heapq
import math

n, m = map(int, input().split())
A = list(map(lambda x: -x, map(int, input().split())))
heapq.heapify(A)
for _ in range(m):
    tmp = heapq.heappop(A)
    tmp = math.ceil(tmp / 2)
    heapq.heappush(A, tmp)
print(-sum(A))
### BUGGY CODE ###


import queue

n,m=map(int,input().split())

G=[[] for i in range(n)]

for _ in range(m):
 y,yy=map(int,input().split())
 y-=1
 yy-=1
 G[y].append(yy)
 G[yy].append(y)

q=queue.Queue()

vis=[0]*n
mae=[-1]*n

q.put([0,0])
while q.empty()==False:
 r=q.get()
 if vis[r[0]]==1:
  continue
 vis[r[0]]=1
 mae[r[0]]=r[1]
 for v in G[r[0]]:
  q.put([v,r[0]])

print("Yes")
for i in range(1,n):
 print(mae[i]+1)

### FIXED CODE ###


import queue

n,m=map(int,input().split())

G=[[] for i in range(n)]

for _ in range(m):
 y,yy=map(int,input().split())
 y-=1
 yy-=1
 G[y].append(yy)
 G[yy].append(y)

q=queue.Queue()

vis=[0]*n
mae=[-1]*n

q.put([0,0])
while q.empty()==False:
 r=q.get()
 if vis[r[0]]==1:
  continue
 vis[r[0]]=1
 mae[r[0]]=r[1]
 for v in G[r[0]]:
  if vis[v]==0:
   q.put([v,r[0]])

print("Yes")
for i in range(1,n):
 print(mae[i]+1)
### BUGGY CODE ###

#https://atcoder.jp/contests/abc139/tasks/abc139_d

n = int(input())

a = 0
for i in range(1,n):
    a+=i

print(a)

### FIXED CODE ###

#https://atcoder.jp/contests/abc139/tasks/abc139_d

n = int(input())

a = (n-1)*n // 2

print(a)
### BUGGY CODE ###

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    s = input()
    q = input_int()
    inverse = False
    for _ in range(q):
        data = input().split()
        if len(data) == 1:
            inverse = not inverse
        else:
            if (data[1] == "1" and not inverse) or (data[1] == "2" and inverse):
                s = data[2] + s
            else:
                s = s + data[2]
    if inverse:
        print(s[::-1])
    else:
        print(s)
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
# sys.setrecursionlimit(100000)
from collections import deque


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    s = deque(list(input()))
    q = input_int()
    inverse = False
    for _ in range(q):
        data = input().split()
        if len(data) == 1:
            inverse = not inverse
        else:
            if (data[1] == "1" and not inverse) or (data[1] == "2" and inverse):
                s.appendleft(data[2])
            else:
                s.append(data[2])
    if inverse:
        print("".join(reversed(s)))
    else:
        print("".join(s))
    return


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

N=int(input())
S=input()

# Zアルゴリズムで解く

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]
    length = len(subS)
    if length <= max_num:
        break
    
    A=[0 for i in range(length-max_num)]

    for i in range(1,length-max_num):
        if i+ A[i-c] < c+A[c]:
            A[i] = A[i-c]
        else:
            j=max(0,c+A[c]-i)
            while i+j<length and subS[j]==subS[i+j]:
                j+=1
            A[i]=j
        if max_num<A[i] and i>=A[i]:
            max_num = A[i]
print(max_num)

### FIXED CODE ###

N=int(input())
S=input()

# Zアルゴリズムで解く

def z_algorithm(S):
    N=len(S)
    A = [N] + [0]*(N-1)
    
    left=1
    length=0
    
    while left < N:
        
        # prefixが同じ間length加算
        while left + length < N and S[length] == S[left+length]:
            length += 1
        
        # prefixの一致数保存
        A[left] = length
        
        # 一文字一致していなければ戻る
        if length == 0:
            left+=1
            continue
        
        # lengthの分だけleftとindexの間を埋めていく(はみ出ていないとこまで)
        k=1
        while k+left < N and k+A[k]<length:
            A[left+k] = A[k]
            k += 1
            
        left += k
        length -= k
    return A

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]
    A=z_algorithm(subS)
    for i,a in enumerate(A):
        if i>=a and max_num<a:
            max_num=a
print(max_num)
### BUGGY CODE ###

# from scipy.special import comb
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
all = (2**n - 1)%mod

def comb(n, r):
  c = 1
  m = 1
  r = min(n-r, r)
  for i in range(r):
    c = c * (n - i) % mod
    m = m * (i + 1) % mod
  return c * pow(m, mod-2, mod) % mod

nca = comb(n, a)
ncb = comb(n, b)
all -= nca + ncb
print(all%mod)


### FIXED CODE ###

n, a, b = map(int, input().split())
mod = pow(10, 9) + 7
all = pow(2, n, mod) - 1

def comb(n, r):
  c = 1
  m = 1
  r = min(n-r, r)
  for i in range(r):
    c = c * (n - i) % mod
    m = m * (i + 1) % mod
  return c * pow(m, mod-2, mod) % mod

nca = comb(n, a)
ncb = comb(n, b)
all -= nca + ncb
print(all%mod)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Aug  6 17:34:40 2018

@author: Yuki
"""

N = int(input())
S = input()
res = []
for i, n_ban in enumerate(S):
    # Westからn_ban目の人をリーダーとしたときに何人を変える必要があるか
    # n_banについて全探索
    # 自分よりEast側かつEastを向いてる人の人数と
    # 自分よりWest側かつWestを向いてる人の人数の合計
    E_cnt = 0
    W_cnt = 0
    E_line = S[i:]
    W_line = S[:i]
    E_cnt = E_line.count('E')
    W_cnt = W_line.count('W')
    if n_ban == 'E':
        E_cnt -= 1
    res.append(E_cnt+W_cnt)

print(min(res))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Aug  6 17:34:40 2018

@author: Yuki
"""

N = int(input())
S = input()
res = []

res.append(S[1:].count('E'))
for i in range(1, len(S)):
    if S[i] == 'E':
        tmp = res[-1]-1
        if S[i-1] == 'W':
            tmp += 1
        
    elif S[i] == 'W':
        tmp = res[-1]
        if S[i-1] == 'W':
            tmp += 1
    res.append(tmp)
    

print(min(res))
### BUGGY CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ set() for i in range(n) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[v].add(u)
s,t = inm()
s -= 1
t -= 1

reach2 = [ [] for i in range(n) ]
m2done = [ False for i in range(n) ]
reach3 = [ [] for i in range(n) ]
m3done = [ False for i in range(n) ]

def mark(f):
    x = set()
    if not m2done[f]:
        y = set()
        for v1 in dst[f]:
            for v2 in dst[v1]:
                y.add(v2)
        reach2[f] = list(y)
        m2done[f] = True

    for v2 in reach2[f]:
                for v3 in dst[v2]:
                    if v3 == f:
                        continue
                    x.add(v3)
    reach3[f] = list(x)
    m3done[f] = True

dist = [-1] * n
dist[t] = 0
q = deque([(t,0)])
while len(q)>0:
    v,d = q.popleft()
    if not m3done[v]:
        mark(v)
    for nxt in reach3[v]:
        if dist[nxt] > -1:
            continue
        if nxt==s:
            print(d+1)
            exit()
        dist[nxt] = d+1
        q.append((nxt,d+1))
print(-1)


### FIXED CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n*3) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v+n)
    dst[u+n].append(v+n*2)
    dst[u+n*2].append(v)
s,t = inm()
s -= 1
t -= 1
ddprint(dst)

dist = [-1] * (n*3)
dist[s] = 0
q = deque([s])
while len(q)>0:
    v = q.popleft()
    #ddprint('v='+str(v))
    for nxt in dst[v]:
        #ddprint('nxt='+str(nxt))
        if nxt==t:
            print((dist[v]+1)//3)
            exit()
        if dist[nxt] > -1:
            continue
        dist[nxt] = dist[v]+1
        q.append(nxt)
    #ddprint(dist)
    #ddprint(q)
print(-1)
### BUGGY CODE ###

import heapq
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort(reverse=True)
F.sort()

L = []
for i in range(N):
  heapq.heappush(L, (-A[i]*F[i],A[i],F[i]))

for i in range(K):
  temp = heapq.heappop(L)
  rep = (-(temp[1]-1)*temp[2], (temp[1]-1), temp[2])
  heapq.heappush(L, rep)
ans = heapq.heappop(L)
print(-1*ans[0])


### FIXED CODE ###

def solve(B,G,x):
  sums = 0
  for i in range(N):
    req = B[i] - x//G[i] 
    sums += max(0,req)
  if sums <= K:
    return True
  else:
    return False

N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort(reverse=True)
F.sort()

if sum(A) <= K:
  print("0")
  exit(0)

L = []
MAX = 0
for i in range(N):
  temp = A[i]*F[i]
  MAX = max(MAX,temp)
ng = 1
ok = MAX+1
while abs(ng-ok) > 1:
  mid = (ok+ng)//2
  #print(mid,solve(A,F,mid))
  if solve(A,F,mid):
    ok = mid
  else:
    ng = mid
print(ok)
### BUGGY CODE ###

N,K = (int(x) for x in input().split())
A = [int(x) for x in input().split()]

#print(N)
#print(K)
#print(A)

preX = 0
nowX = 1

for i in range(K,N+1):
#  print(str(i)+'学期')
  if i == K:
    for x in range(K):
      nowX *= A[x]
  else:
    nowX = int(preX / A[i-K-1]) * A[i-1]
#    print(str(preX) +', '+ str(nowX))
    if preX < nowX:
      print('Yes')
    else:
      print('No')
  preX = nowX
  

### FIXED CODE ###

N,K = (int(x) for x in input().split())
A = [int(x) for x in input().split()]

#print(N)
#print(K)
#print(A)

preX = 0
nowX = 1

for i in range(K+1,N+1):
#  print(str(i)+'学期')
#  if i == K:
#    for x in range(K):
#      nowX *= A[x]
#  else:
#    nowX = int(preX / A[i-K-1]) * A[i-1]
#    print(str(preX) +', '+ str(nowX))
#    if preX < nowX:
#      print('Yes')
#    else:
#      print('No')
#  preX = nowX

  if A[i-K-1] < A[i-1]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*n
        self.rank=[-1]*n

    def Find_Root(self,x):
        if self.root[x]<0:return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def size(self,x):
        return -self.root[self.Find_Root(x)]

    def members(self,x):
        root=self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i)==root]

    def roots(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

    def group_count(self):
        return len(self.roots())


n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

UnionFind=UnionFind(n+1)
for a,b in AB:
    UnionFind.Unite(a,b)

A=UnionFind.group_members()
ans=0
for i in A:
    ans=max(ans,len(A[i]))
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline


class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*n
        self.rank=[-1]*n

    def Find_Root(self,x):
        if self.root[x]<0:return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def size(self,x):
        return -self.root[self.Find_Root(x)]

    def members(self,x):
        root=self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i)==root]

    def roots(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

    def group_count(self):
        return len(self.roots())


n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

UnionFind=UnionFind(n+1)
for a,b in AB:
    if UnionFind.isSameGroup(a,b) is False:
        UnionFind.Unite(a,b)

ans=0
for i in range(1,n+1):
    cnt=UnionFind.size(i)
    if ans<cnt:
        ans=cnt
print(ans)
### BUGGY CODE ###

s=str(input())
n=len(s)
ans=0
for i in range(3,n):
  for j in range(i-2):
    if int(s[j:i+1])%2019==0:
      ans+=1
print(ans)


### FIXED CODE ###

s=input()
s=s[::-1]
n=len(s)
count=[0]*2019
count[0]=1
num,d=0,1

for i in s:
  num+=int(i)*d
  num%=2019
  d*=10
  d%=2019
  count[num]+=1

ans=0
for i in count:
  ans+=i*(i-1)//2
  
print(ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
m2 = [1 for i in range(60)]
for i in range(1,60):
    m2[i] = (m2[i-1]*2)%mod

n1 = np.zeros(60,dtype=int)
for i in a:
    sai = list(map(lambda x:int(x),str(format(i,'060b'))))
    n1 += sai

ans = 0
for i in range(60):
    ans = (ans+((n1[i]*(n-n1[i]))%mod*m2[59-i])%mod)%mod

print(ans)


### FIXED CODE ###

#https://atcoder.jp/contests/abc147/submissions/12994515を見た

import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
mod = 10**9+7
m2 = [1 for i in range(60)]
for i in range(1,60):
    m2[i] = (m2[i-1]*2)%mod

ans = 0
for i in range(60):
    ni = np.count_nonzero(a&1)
    ans = (ans+ni*(n-ni)%mod*m2[i])%mod
    a >>= 1

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

import numpy as np
n,A=tuple(map(lambda x:int(x),input().split()))
x=tuple(map(lambda x:int(x),input().split()))
dp=np.zeros((n+1,n+1,n*A+1), dtype=int)
dp[:,0,0]=1
for i in range(1,n+1):
    for k in range(1, n+1):
        for j in range(1,n*A+1):
            if k<=i and 0<=j-x[i-1]:
                dp[i,k,j]=dp[i-1,k,j]+dp[i-1,k-1,j-x[i-1]]
            else:
                dp[i,k,j]=dp[i-1,k,j]
c=0
for k in range(1,n+1):
    c+=dp[n,k,k*A]
print(c)


### FIXED CODE ###

import numpy as np
n,avea=tuple(map(lambda x:int(x),input().split()))
x=list(map(lambda x:int(x), input().split()))
x=np.array(x)
x=x-avea
w=max(abs(min(x)),abs(max(x)))*n
dp=np.zeros((n+1,2*w+1),dtype=int)
dp[0,w]=1
for i in range(n):
    for j in range(2*w+1):
        if 0<=j-x[i]<=2*w:
            dp[i+1,j]=dp[i,j]+dp[i,j-x[i]]
        else:
            dp[i+1,j]=dp[i,j]
print(dp[n,w]-1)
### BUGGY CODE ###

a, b, k = map(int, input().split(' '))
ab = [i for i in range(a, b+1)]
if len(ab) <= 2*k:
  abp = [print(i) for i in ab]
else:
  del ab[k:-k]
  abp = [print(i) for i in ab]

### FIXED CODE ###

a, b, k = map(int, input().split(' '))
if b - a + 1 < 2 * k:
  for i in range(a, b + 1):
    print(i) 
else:
  for i in range(a, a + k):
    print(i)
  for i in range(b - k + 1, b + 1):
    print(i)
### BUGGY CODE ###

# 大きい数用
def modPow(a, n, p):
    if n == 0:
        return 1
    if n == 1:
        return a
    if n % 2 == 1:
        return (a * (modPow(a, n//2, p) ** 2)) % p
    else:
        return (modPow(a, n//2, p) ** 2) % p


N, P = map(int, input().split())
S = input()

if P != 2 and P != 5:
    p_array = [0] * P
    mod = 0
    for i, s in enumerate(S[::-1]):
        s = int(s)
        mod = (mod + s * modPow(10, i, P)) % P
        p_array[mod] += 1

    ans = 0
    for i, p in enumerate(p_array):
        if i == 0:
            ans += p
        ans += (p * (p-1) // 2)

    print(int(ans))

else:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += (i+1)
    print(ans)


### FIXED CODE ###

N, P = map(int, input().split())
S = input()

if P != 2 and P != 5:
    p_array = [0] * P
    mod = 0
    amari = 1
    for i, s in enumerate(S[::-1]):
        s = int(s)
        mod = (mod + s * amari) % P
        amari = amari * 10 % P
        p_array[mod] += 1

    ans = 0
    for i, p in enumerate(p_array):
        if i == 0:
            ans += p
        ans += (p * (p-1) // 2)

    print(int(ans))

else:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += (i+1)
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
abs_a = []
minus = 0

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

if minus % 2 == 0:
  for i in range(n):
    abs_a.append(abs(a[i]))
  print(sum(abs_a))
else:
  for i in range(n):
    abs_a.append(abs(a[i]))
    min_abs_a = min(abs_a)
  print(sum(abs_a)-min_abs_a*2)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
abs_a = []
minus = 0

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

for i in range(n):
  abs_a.append(abs(a[i]))
  
if minus % 2 == 0:
  print(sum(abs_a))
else:
  min_abs_a = min(abs_a)
  print(sum(abs_a)-min_abs_a*2)
### BUGGY CODE ###

import math
N, A, B = (int(x) for x in input().split(' '))
ans = 0
#
for i in range(N):
  if i % (A+B) < A:
    ans += 1
#結果出力
print(ans)

### FIXED CODE ###

import math
N, A, B = (int(x) for x in input().split(' '))
tmp = A * math.floor(N/(A+B))

if ( N % (A+B) ) > A:
  print(tmp+A) 
else:
  print(tmp+( N % (A+B)))
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

for i in range(N-1):
    print(A.count(i+1))
print(0)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

P = [0]*N
for i in range(N-1):
    P[A[i]-1] += 1

for i in range(N):
    print(P[i])
### BUGGY 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 = -30
	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 = -30
	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)

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

n, k = map(int, input().split())
h = list(map(int, input().split()))

ans = 0
for i in range(n-k):
  ans += min(h)
  h.remove(min(h))
  
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
h2 = sorted(h)

if n<k:
  print(0)
else:
  print(sum(h2[0:n-k]))
### BUGGY CODE ###

from collections import deque
def solve():
    n = int(input())
    dp = deque([[False]*(n+1)])
    dp[0][0] = True
    way = [1] + [6**i for i in range(1,9) if 6**i <= n] + [9**i for i in range(1,7) if 9**i <= n]
    while True:
        newline = [False] * (n+1)
        for w in way:
            for i in range(0, n+1):
                if i - w < 0: continue
                if dp[0][i-w]: newline[i] = True
                if newline[n]:
                    return len(dp)
        dp.appendleft(newline)

print(solve())

### FIXED CODE ###

def solve():
    n = int(input())
    dp = [True] + [False]*(n+1)
    way = [1] + [6**i for i in range(1,9) if 6**i <= n] + [9**i for i in range(1,7) if 9**i <= n]
    loop_counter = 0
    while True:
        loop_counter += 1
        newdp = [False] * (n+1)
        for w in way:
            for i in range(w, n+1):
                if newdp[i]: continue
                if dp[i-w]: newdp[i] = True
                if newdp[n]: 
                    return loop_counter
        dp = [x for x in newdp]

print(solve())