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

n = int(input())
A = sorted(list(map(int, input().split())))
c = 1
for i in range(n-1, 0, -1):
  if sum(A[:i])*2 >= A[i]:
    c += 1
  else:
    print(c)
    exit()
print(n)  

### FIXED CODE ###

n = int(input())
A = sorted(list(map(int, input().split())))
c = 1
sumA = sum(A)
for i in range(n-1, 0, -1):
  sumA -= A[i]
  if sumA*2 >= A[i]:
    c += 1
  else:
    print(c)
    exit()
print(n)
### BUGGY CODE ###

def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list

N,M = map(int,input().split())
L = sorted(make_divisor_list(M),reverse = True)
for j in L :
    if j <= M//N :
        if (M - j*(N-1)) % j == 0 :
            print(j)
            break
            

### FIXED CODE ###

import numpy as np
from math import sqrt
ANS = []
N,M = map(int,input().split())
L = np.arange(1,int(sqrt(M))+1,dtype=int)
#L = sorted(L,reverse = True)
for i in L :
    if M % i == 0 :
        ANS.append(i)
        ANS.append(M//i)
ANS = sorted(ANS,reverse = True)
for j in ANS :
    if j * N <= M :
        print(j)
        break
### BUGGY CODE ###

S=input()
n=len(S)
ans=[]
for i in range(n):
  j=i
  cnt=0
  while(S[j]=='A' or S[j]=='C' or S[j]=='G' or S[j]=='T'):
    cnt+=1
  ans.append(cnt)
print(max(ans))
    

### FIXED CODE ###

s=list(input())
cnt=0
ans=0
l=list("ATCG")
 
for i in s:
    if i in l:
        cnt+=1
        ans=max(ans,cnt)
    else:
        cnt=0
print(ans)
### BUGGY CODE ###

import numpy as np

n, k = [int(i) for i in input().split()]
s = input()

ones = [len(x) for x in s.replace('0', ' ').split()]
zeros = [len(x) for x in s.replace('1', ' ').split()]

if s[0]=='0':
  ones = [0] + ones
if s[-1]=='0':
  ones = ones + [0]

if k >= len(zeros):
  result = n
else: 
  result = [
    np.sum(ones[i:i+k+1]) + np.sum(zeros[i:i+k])
    for i in range(len(zeros)-k+1)]
  result = max(result)

print(result)

### FIXED CODE ###

import numpy as np

n, k = [int(i) for i in input().split()]
s = input()

ones = [len(x) for x in s.replace('0', ' ').split()]
zeros = [len(x) for x in s.replace('1', ' ').split()]

if s[0]=='0':
  ones = [0] + ones
if s[-1]=='0':
  ones = ones + [0]
  
ones = np.array(ones)
zeros = np.array(zeros)

if k >= len(zeros):
  result = n
else: 
  result = [
    np.sum(ones[i:i+k+1]) + np.sum(zeros[i:i+k])
    for i in range(len(zeros)-k+1)]
  result = max(result)

print(result)
### BUGGY CODE ###

N = int(input())

arr = []
counter = 0

for i in range(N):
    string = input()
    if not string in arr:
        counter += 1
        arr.append(string)

print(counter)

### FIXED CODE ###

N = int(input())

arr = []

for i in range(N):
    arr.append(input())

print(len(set(arr)))
### BUGGY CODE ###

a, b = map(int, input().split())
minus = 0
for i in range(a, b + 1):
    if i == 0:
        print('Zero')
        break
    elif i < 0:
        minus += 1
else:
    if minus % 2:
        print('Negative')
    else:
        print('Positive')


### FIXED CODE ###

a, b = map(int, input().split())

if a * b <= 0:
    print('Zero')
elif 1 <= a:
    print('Positive')
else:
    if (b - a) %2 == 0:
        print('Negative')
    else:
        print('Positive')
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    
    # 根を検索する関数
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    # 結合(unite)する関数
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    # 根が同じかどうか判定する関数
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


if __name__ == "__main__":
    N,M = map(int, input().split())
    uf = UnionFind(N)

    A, B = [0] * M, [0] * M
    for i in range(M):
        A[i], B[i] = [int(j) for j in input().split()]

    total = int(N * (N-1) / 2)
    ans = []
    for i in range(M):
        count = 0
        for j in range(1,N):
            for k in range(j+1,N+1):
                if uf.same_check(j, k):
                    count += 1
        uf.union(A[-(i+1)], B[-(i+1)])
        ans.append(total - count)
    
    for i in (reversed(ans)):
        print(i)


### FIXED CODE ###

class UnionFind_size:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.size = [1] * (n+1)
    
    # 根を検索する関数
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    # 結合(unite)する関数
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
           
    # 同じグループに属するかを判定する関数
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    # 要素が属する木のサイズを返す関数
    def get_size(self, x):
        return self.size[self.find(x)]
    
    # グループ数を返す関数
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c


if __name__ == "__main__":
    N,M = map(int, input().split())
    uf = UnionFind_size(N)

    A, B = [0] * M, [0] * M
    for i in range(M):
        A[i], B[i] = [int(j) for j in input().split()]

    total = int(N * (N-1) / 2)
    ans = [total]
    for i in range(M-1):
        if uf.same_check(A[-(i+1)], B[-(i+1)]):
            ans.append(ans[i])
        else:
            ans.append(ans[i] - uf.get_size(A[-(i+1)]) * uf.get_size(B[-(i+1)]))
        uf.unite(A[-(i+1)], B[-(i+1)])
    
    for i in (reversed(ans)):
        print(i)
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
# print(P)
E = [(p*(p+1))/(2*p) for p in P]
# print([sum(E[i:i+K]) for i in range(N-K+1)])
print(max([sum(E[i:i+K]) for i in range(N-K+1)]))


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
# print(P)
E = [(p*(p+1))/(2*p) for p in P]
# print([sum(E[i:i+K]) for i in range(N-K+1)])
S = [0]
for i in range(N):
    S.append(S[i] + E[i])
print(max([S[i+K] - S[i] for i in range(N-K+1)]))
### BUGGY CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def main():
    K = int(input())
    s = sum([gcd(i+1, j+1, k+1) for i in range(K) for j in range(K) for k in range(K)])

    print(s)


if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def main():
    K = int(input())
    s = sum([gcd(i+1, j+1, k+1) for i in range(K) for j in range(K) for k in range(K)])

    print(s)


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

from functools import reduce
import collections


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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

l = {}
answer = 0
for aa in a:
    c = collections.Counter(prime_factorize(aa))
    cc.append(c)
    for k in c.keys():
        if k in l:
            l[k] = max(c[k], l[k])
        else:
            l[k] = c[k]

for idx, aa in enumerate(a):
    ll = 1
    c = cc[idx]
    for k in l.keys():
        if k in c:
            ll = ll * (k ** (l[k] - c[k]))
        else:
            ll = ll * (k ** l[k])
    answer += ll
    if answer >= 10 ** 9 + 7:
        answer = answer % (10 ** 9 + 7)

print(answer)


### FIXED CODE ###

# import math
# import fractions

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

mod = 10 ** 9 + 7


def prime_factorize(n):
    a = {}
    while n % 2 == 0:
        if 2 not in a:
          a[2] = 0
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in a:
              a[f] = 0
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
      if n not in a:
        a[n] = 0
      a[n] += 1
    return a


# 最小公倍数を素因数分解した形で持つ
l = prime_factorize(a[0])
# print(l)
# xs = {}
# xs[a[0]] = prime_factorize(a[0])
for i in range(1, n):
  ps = prime_factorize(a[i])
  # print(ps)
  # xs[a[i]] = ps
  for k, v in ps.items():
    if k in l:
      l[k] = max(v, l[k])
    else:
      l[k] = v

# print(l)
# print(xs)

L = 1
for k, v in l.items():
  L = L * pow(k, v, mod) % mod

answer = 0
for x in a:
  answer = (answer + L * pow(x, mod - 2, mod)) % mod
print(answer)
### BUGGY CODE ###

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

L.sort()
c=[]
for i in range(2**n):
  tmp=[]
  for j in range(n):
    if i>>j&1:
      tmp.append(L[j])
  if len(tmp)==3 and tmp not in c:
    c.append(tmp)
ans=0
for a,b,c in c:
  if b-a<c and c<a+b:
    ans+=1
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
L=list(map(int,input().split()))

L.sort()
ans=0
for i in range(n):
  for j in range(i+1,n):
    index=bisect.bisect_left(L,L[i]+L[j])
    ans+=index-(j+1)
    
print(ans)
### BUGGY CODE ###

import itertools

iCnt = int(input())
v = list(input())

vAns = []
vProduct = []
iOnIndex = 0
while iOnIndex + 1 < iCnt:
    iLen = len(v[-iCnt + iOnIndex + 1:])
    vProduct = list(itertools.product([0, 1], repeat=iLen))
    for p in vProduct:
        sChk = v[iOnIndex]
        iP_Len = len(p)
        for i in range(iP_Len):
            if p[i] == 1:
                if v[iOnIndex + i + 1] not in sChk:
                    sChk += v[iOnIndex + i + 1]
                else:
                    sChk = "NG"
                    break
        if "NG" not in sChk: vAns.append(sChk)
    iOnIndex += 1
vAns.append(v[iCnt - 1])
print(len(vAns) % (10 ** 9 + 7))

### FIXED CODE ###

from collections import defaultdict

iCnt = int(input())
S = input()
M = 10**9 + 7

vCntDct = defaultdict(int)

for s in S:
    vCntDct[s] += 1

ans = 1
for v in vCntDct.values():
    ans *= (v + 1)
    ans %= M

print(ans - 1)
### BUGGY CODE ###


#from math import gcd
import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)

K = int(input())

def gcd(x,y):
    while y:
        x, y = y, x % y
    return x

ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(gcd(i,j), k)
print(ans)


### FIXED CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

K = int(input())
mod = 10**9 + 7

N = 3

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

ans = 0

M = np.zeros(K+1, dtype=int)

for i in range(K, 0, -1):
#    print(i)
    M[i] += pow(K//i, N)
    
    for j in range(2,K//i+1):
        j *= i
        M[i] -= M[j]
    
    ans += M[i] * i
    
        
print(ans)
### BUGGY CODE ###

h,w = map(int,input().split())
s = [input() for _ in range(h)]
dp = [[float('inf')]*w for i in range(h)]
dp[0][0] = 1 if s[0][0]=='#' else 0
q = [[0,0]]
while q:
    x,y = q.pop()
    a = 1 if s[x][y]=='#' else 0
    if x+1<h:
        dp[x+1][y] = min(dp[x][y]+a,dp[x+1][y])
        q.append([x+1,y])
    if y+1<w:
        dp[x][y+1] = min(dp[x][y]+a,dp[x][y+1])
        q.append([x,y+1])
print(dp[h-1][w-1])



### FIXED CODE ###

h,w = map(int,input().split())
s = [input() for _ in range(h)]
dp = [[float('inf')]*w for i in range(h)]
dp[0][0] = 1 if s[0][0]=='#' else 0
for x in range(h):
    for y in range(w):
        if x+1<h:
            a = 1 if s[x][y]=='.' and s[x+1][y]=='#' else 0
            dp[x+1][y] = min(dp[x][y]+a,dp[x+1][y])
        if y+1<w:
            a = 1 if s[x][y]=='.' and s[x][y+1]=='#' else 0
            dp[x][y+1] = min(dp[x][y]+a,dp[x][y+1])

print(dp[h-1][w-1])
### BUGGY CODE ###

#入力
N = int(input())
maxmembers={}
for i in range(5):
    maxmembers[i] = int(input())

citypeople = [N,0,0,0,0,0]
flag = bool(False)
time = 0
'''
for i in range(6):
    print(citypeople[i],end=' ')
print('')
'''
while True:
    for i in reversed(range(1,6)):
        if citypeople[i-1] > maxmembers[i-1]:
            citypeople[i] += maxmembers[i-1]
            citypeople[i-1] -= maxmembers[i-1]
        else:
            citypeople[i] += citypeople[i-1]
            citypeople[i-1] = 0
    time += 1
    """
    for i in range(6):
        print(citypeople[i],end=' ')
    print('')
    """
    if citypeople[5] == N:
        break

print(time)


### FIXED CODE ###

#入力
N = int(input())
maxmembers={}
for i in range(5):
    maxmembers[i] = int(input())

#シミュレーション
'''
citypeople = [N,0,0,0,0,0]
flag = bool(False)
time = 0

for i in range(6):
    print(citypeople[i],end=' ')
print('')

while True:
    for i in reversed(range(1,6)):
        if citypeople[i-1] > maxmembers[i-1]:
            citypeople[i] += maxmembers[i-1]
            citypeople[i-1] -= maxmembers[i-1]
        else:
            citypeople[i] += citypeople[i-1]
            citypeople[i-1] = 0
    time += 1
    
    for i in range(6):
        print(citypeople[i],end=' ')
    print('')
    
    if citypeople[5] == N:
        break

print(time)
'''
#ボトルネックを全部に適用する
mintransportation = maxmembers[0]
for i in range(1,5):
    if maxmembers[i] < mintransportation:
        mintransportation = maxmembers[i]

if N % mintransportation == 0:
    time = int(N / mintransportation) + 4
else:
    time = int(N / mintransportation) + 5
print(time)
### BUGGY CODE ###

n = int(input())
h = [int(i) for i in input().split()]
num = []
for i in range(len(h)):
  num += [h.index(i+1)+1]
print(*num, sep=" ")

### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
num = [0 for i in range(n)]
for i in range(len(h)):
  num[h[i]-1] = i+1
print(' '.join(map(str, num)))
### BUGGY CODE ###

N, M= map(int, input().split())
a =[str(input()) for _ in range(M)]
DP = [0]*(N+2)
num = 1000000007
DP[0] = 1
for i in range(N):
  if str(i) in a:
    DP[i] = 0
  else:
    DP[i] = DP[i] % num 
    if i < N:
      DP[i+1] += DP[i]
      DP[i+2] += DP[i]
print(DP[-2]%num)

### FIXED CODE ###

N, M, = map(int, input().split())
a = set([int(input()) for _ in range(M)])
DP = [0]*(N+2)
num = 1000000007
DP[0] = 1
for i in range(N):
  if i in a:
    DP[i] = 0
  else:
    DP[i] = DP[i] % num 
    if i < N:
      DP[i+1] += DP[i]
      DP[i+2] += DP[i]
print(DP[-2]%num)
### BUGGY CODE ###

import numpy as np

n, m, k = map(int, input().split())
a = np.array([0] + list(map(int, input().split())))
b = np.array([0] + list(map(int, input().split())))

for i in range(n):
    a[i+1] += a[i]

for i in range(m):
    b[i+1] += b[i]

ans = 0

for i in range(n+1):
    if k < a[i]:
        continue
    l = 0
    r = m + 1
    while r - l > 1:
        mid = (l + r) // 2
        if b[mid] + a[i] <= k:
            l = mid
        else:
            r = mid

    ans = max(ans, i + l)

print(ans)


### FIXED CODE ###

import numpy as np

n, m, k = map(int, input().split())
a = np.array([0] + list(map(int, input().split())))
b = np.array([0] + list(map(int, input().split())))

for i in range(n):
    a[i+1] += a[i]

for i in range(m):
    b[i+1] += b[i]

ans = 0
r = m

for i in range(n+1):
    while 0 < r and k < a[i] + b[r]:
        r -= 1

    if a[i] + b[r] <= k:
        ans = max(ans, i + r)

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

a,b,k=map(int,input().split())
for x in sorted(set(range(a, b + 1)) & (set(range(a, a + k)) | set(range(b - k + 1, b + 1)))):
  print(x)

### FIXED CODE ###

a,b,k=map(int,input().split())
l = range(a, b + 1) if b - a + 1 <= k else sorted(set(range(a, a + k)) | set(range(b - k + 1, b + 1)))
for i in l: 
  print(i)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
cost = [10 ** 9] * n
cost[0] = 0
for i in range(1, n):
  cur_h = h[i]
  for jump in range(1, k + 1):
    if i < jump:
      break
    cost[i] = min(cost[i], cost[i-jump] + abs(h[i-jump] - cur_h))
print(cost[-1])


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
h = np.array(input().split(), dtype=np.int)
cost = np.zeros(n, dtype=np.int)
for i in range(1, n):
  cur_h = h[i]
  start = max(0, i - k)
  cost[i] = np.min(cost[start : i] + np.abs(h[start : i] - cur_h))
print(cost[-1])
### BUGGY CODE ###

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

for i in range(n):
    B=[0]+A[:i]+A[i+1:]+[0]
    cnt=0
    for j in range(n):
        cnt+=abs(B[j+1]-B[j])
    print(cnt)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
A=[0]+A+[0]
cnt=0
for i in range(n+1):
    cnt+=abs(A[i+1]-A[i])

for i in range(1,n+1):
    if (A[i-1]-A[i])*(A[i]-A[i+1])>=0:
        print(cnt)
    else:
        print(cnt-abs(A[i-1]-A[i])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]))
### BUGGY CODE ###

N = int(input())
L = input().split()
tri = 0
for i in range(0,N):
    L[i] = int(L[i])
for i in range(0,N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[i] < L[j] + L[k] and L[j] < L[i] + L[k] and L[k] < L[j] + L[i]:
                tri += 1
print(tri)

### FIXED CODE ###

N = int(input())
L = input().split()
tri = 0
for i in range(0,N):
    L[i] = int(L[i])
L.sort()
for i in range(0,N):
    k = i
    for j in range(i+1,N):
        while(k < N and L[k] < L[i] + L[j]):
            k += 1
        tri += k-j-1
print(tri)
### BUGGY CODE ###

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

dp = [[dict() for i in range(4)] for i in range(N + 1)]
dp[0][0][''] = True
for i in range(N):
    for j in range(4):
        for k, v in dp[i][j].items():
            dp[i+1][j][k] = True
            if j <= 2:
                dp[i+1][j+1][k+S[i]] = True

print(len(dp[-1][-1]))

### FIXED CODE ###

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

cnt = 0
for i in range(1000):
    n = '{:03d}'.format(i)
    i = 0
    for d in n:
        try:
            i = S.index(d, i) + 1
        except ValueError:
            break
    else:
        cnt += 1

print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

a, b, x = map(int, input().split(' '))
p = -1
ans = 0
while True:
    p += 1
    num = x * p
    if num < a:
        continue
    if num > b:
        break
    ans += 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

a, b, x = map(int, input().split(' '))
m = b//x+1
n = 0
if a > 0:
    n = (a-1)//x+1
ans = m - n
print(ans)
### BUGGY CODE ###

N = int( input())
S = [ input() for _ in range(N)]
ans = 0
for k in range(N):
    check = True
    for i in range(N):
        for j in range(i+1,N):
            if not S[i][(j+k)%N] == S[j][(i+k)%N]:
                check = False
                break
        if not check:
            break
    if check:
        ans += N
print(ans)


### FIXED CODE ###

N = int( input())
S = [ input() for _ in range(N)]
ans = 0
for k in range(N):
    check = True
    for i in range(N):
        for j in range(i+1,N):
            if not S[i][(j+k)%N] == S[j][(i+k)%N]:
                check = False
                break
        if not check:
            break
    if check:
        ans += N
print(ans)
### BUGGY CODE ###

n = int(input())

print(0)
s0 = str(input())

print(n-1)

def is_ok(x):
    print(x)
    s = str(input())
    if s == s0:
        return False
    else:
        return True

l = 0
r = n-1
while l+1 < r:
    c = (l+r)//2
    if is_ok(c):
        r = c
    else:
        l = c        


### FIXED CODE ###

def main():
    n = int(input())

    def q(i):
        print(i, )
        s = str(input())
        if s == 'Vacant':
            exit()
        else:
            return s

    x = q(n-1)
    x = q(0)

    def ok(m):
        if m == 0:
            return False
        else:
            if (m%2 == 0 and q(m) != x) or (m%2 == 1 and q(m) == x):
                return True
            else:
                return False

    l = 0
    r = n-1
    while l+1 < r:
        c = (l+r)//2
        if ok(c):
            r = c
        else:
            l = c

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

#dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]+1:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    print(array[-1][-1])



### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
### BUGGY CODE ###

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

def solver(k):
    global ans
    ans = [k]
    if k % 2 == 1:
        return False
    b = k
    for i in range(N - 1):
        b = 2 * A[i] - b
        ans.append(b)
        if b % 2 == 1 or b < 0:
            return False
    if ans[0] + ans[-1] == 2 * A[-1]:
        return True
    else:
        return False

for i in range(total // 2 + 1):
    if solver(2 * i):
        print(" ".join(map(str, ans)))
        exit()

### FIXED CODE ###

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

def solver(k):
    global ans
    ans = [k]
    for i in range(N - 1):
        ans.append(2 * A[i] - ans[i])
    if not ans[0] + ans[-1] == 2 * A[-1]:
        x = (2 * A[-1] - ans[0] - ans[-1]) // 2
        for i in range(N):
            if i % 2 == 0:
                ans[i] += x
            else:
                ans[i] -= x
solver(0)
print(" ".join(map(str, ans)))
### BUGGY CODE ###

import math
honsu,hp=map(int , input().split())
huru=[]
nageru=[]
for i in range(honsu):
  a,b=input().split()
  huru+=[int(a)]
  nageru+=[int(b)]
cc=list(filter(lambda v:v>=max(huru) , nageru))
cou=0
for i in reversed(sorted(cc)):
  hp-=i
  cou+=1
  if hp<=0:
    break
if hp>0:
  cou+=math.ceil(hp/max(huru))
print(cou)

### FIXED CODE ###

from math import ceil
 
N, H = map(int, input().split())
a, b = [], []
 
for _ in range(N):
    a_i, b_i = map(int, input().split())
    a.append(a_i)
    b.append(b_i)
 
max_a = max(a)
b = sorted(b, reverse=True)
ans = float('inf')
th_po = 0
 
for i in range(N):
    th_po += b[i]
    
    if H >= th_po:
        ans_cand = i + 1 + ceil((H - th_po) / max_a)
    else:
        ans_cand = i + 1
    
    ans = min([ans, ans_cand])
 
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
bit_num = 30
A_b = [format(a, '0{}b'.format(bit_num)) for a in A]
S = ''
for i in range(bit_num):
    bit = 0
    for a in A_b:
        if a[i] == '1':
            bit += 1
    if bit % 2 == 0:
        S += '0'
    else:
        S += '1'
#print(S)
B = []
for a in A_b:
    b = ''
    for i in range(bit_num):
        if (int(a[i]) + int(S[i])) % 2 == 0:
            b +='0'
        else:
            b += '1'
    #print(b)
    B.append(int(b, 2))
print(*B)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
bit_num = 30
A_b = [format(a, '0{}b'.format(bit_num)) for a in A]
S = ''
for i in range(bit_num):
    bit = 0
    for a in A_b:
        if a[i] == '1':
            bit += 1
    if bit % 2 == 0:
        S += '0'
    else:
        S += '1'
#print(S)
B = []
for a in A_b:
    b = ''
    for i in range(bit_num):
        if (int(a[i]) + int(S[i])) % 2 == 0:
            b +='0'
        else:
            b += '1'
    #print(b)
    B.append(int(b, 2))
print(*B)