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

import collections

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

list = []
for i in a:
    list.extend(make_divisors(i))

c = collections.Counter(list)
values, counts = zip(*c.most_common())

first = []
second = []
for value, count in zip(values,counts):
    if count == n:
        first.append(value)
    if count == n-1:
        second.append(value)

if len(second) == 0:
    print(max(first))

elif max(first) > max(second):
    print(max(first))

else:
    print(max(second))

### FIXED CODE ###

import copy
n = int(input())
x = [int(i) for i in input().split()]

#ユークリッド互除法の関数の定義
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)


def gcd_multi(n,x):
    if n==1:
        return x[0]
    else:
        element = gcd(x[0], x[1])
        if n==2:
            return element
        else:
            for i in range(2,n):
                element=gcd(element,x[i])
            return element

X=[0 for i in range(n)]
Y=[0 for i in range(n)]

for i in range(1,n):
    X[i]=gcd(X[i-1],x[i-1])

for i in range(n-1)[::-1]:
    Y[i]=gcd(Y[i+1],x[i+1])

Z=[gcd(X[i],Y[i]) for i in range(n)]
print(max(Z))
### BUGGY CODE ###

import numpy as np

N,W = map(int,input().split())
wv = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,W+1])

for i in range(1,N+1):
    for j in range(W+1):
        if j-wv[i-1][0]<0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
print(int(dp[-1][-1]))

### FIXED CODE ###

import numpy as np

N,W = map(int,input().split())
wv = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,W+1])

#　繰り返し回数節約
for i in range(1,N+1):
    dp[i][:wv[i-1][0]] = dp[i-1][:wv[i-1][0]]
    dp[i][wv[i-1][0]:] = np.maximum(dp[i-1][wv[i-1][0]:],dp[i-1][:W+1-wv[i-1][0]]+wv[i-1][1])
print(int(dp[-1,-1]))
### BUGGY CODE ###

island, fune = map(int, input().split(" "))
route = []
for i in range(fune):
    route.append(list(map(int, input().split(" "))))
pos = False
temp = []
for i in range(fune):
    if route[i][0] == 1:
        temp.append(route[i][1])
for j in range(fune):
    if route[j][1] == island:
        if route[j][0] in temp:
            pos = True
            break
print("POSSIBLE") if pos else print("IMPOSSIBLE")

### FIXED CODE ###

island, fune = map(int, input().split(" "))
route = []
for i in range(fune):
    route.append(list(map(int, input().split(" "))))
temp = []
for i in range(fune):
    if route[i][0] == 1:
        temp.append(route[i][1])
for j in range(fune):
    if route[j][1] == island:
        temp.append(route[j][0])


print("POSSIBLE") if len(temp) != len(list(set(temp))) else print("IMPOSSIBLE")
### BUGGY CODE ###

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

a = max(A)
A_max = []
for i in range(N):
  if A[i] != a:
    A_max.append(a)
  else:
    A_ = A[:]
    A_[i] = 0
    A_max.append(max(A_))
    
for i in A_max:
  print(i)

### FIXED CODE ###

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

a = max(A)
A_max = []
A_ = A[:]

for i in range(N):
  if A[i] == a:
    A_[i] = 0
    break
    
a_ = max(A_)    
    
for i in range(N):
  if A[i] != a:
    A_max.append(a)
  else:
    A_max.append(a_)
    
for i in A_max:
  print(i)
### BUGGY CODE ###

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


for i in range(N):
  s = 0
  for j in range(N):
    if j != i:
      s ^= A[j]
  print(s)

### FIXED CODE ###

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

s = 0
for i in range(N):
  s ^= A[i]
for i in range(N):
  si = s
  si ^= A[i]
  print(si)
### BUGGY CODE ###

n=int(input())

for i in range(1,n+1):
    a=i
    if n%a==0:
        b=n//a
        sa=str(a)
        sb=str(b)
        
        #print(a,b,len(sa),len(sb))
        if len(sb)-len(sa)>=0:
            ans=len(sb)
        else:
            #print(b,sb,len(sa),len(sb))
            break

print(ans)

### FIXED CODE ###

n=int(input())

for a in range(1,int(n**0.5+1)):
    if n%a==0:
        b=n//a
        sa=str(a)
        sb=str(b)
        if a<=b:
             ans=len(sb)
        else:
            break

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


n = int(input())
s = input()

print(min([len([x for x in s[:i] if x == 'W']) + \
           len([x for x in s[i+1:] if x == 'E']) \
           for i in range(n)]))


### FIXED CODE ###

n = int(input())
s = input()

turn_east = [0 for x in range(n)]
turn_west = [0 for x in range(n)]
total = [0 for x in range(n)]

for i in range(n):
  if i > 0:
    if s[i-1] == 'W':
      turn_east[i] = turn_east[i-1]+1
    else:
      turn_east[i] = turn_east[i-1]

    if s[n-i] == 'E':
      turn_west[n-1-i] = turn_west[n-i]+1
    else:
      turn_west[n-1-i] = turn_west[n-i]

for j in range(n):
  total[j] = turn_east[j] + turn_west[j]

print(min(total))
### BUGGY CODE ###

n=int(input())
l=[int(s) for s in input().split()]
cnt=0
mx=max(l)
for i in range(1,mx+1):
  k=i
  arc=0
  abc=0
  for j in range(len(l)):
    if l[j]>=k:
      arc+=1
    else:
      abc+=1
  if arc==abc:
    cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
l=[int(s) for s in input().split()]
cnt=0
l.sort()
print(l[n//2]-l[n//2-1])
### BUGGY CODE ###

n,k = map(int,input().split())
w=[]
v=[]
dp =[[0 for i in range(k+1)] for j in range(n+1)]

for i in range(n):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)
for i in range(n):
    for sum_w in range(k+1):
        if sum_w - w[i] >=0:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w - w[i]] + v[i])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

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

### FIXED CODE ###

n,k = map(int,input().split())
w=[]
v=[]
dp =[[0 for i in range(k+1)] for j in range(n+1)]

for i in range(n):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)
for i in range(n):
    for sum_w in range(k+1):
        if sum_w - w[i] >=0:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w - w[i]] + v[i])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

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

def main():
    n = int(input())
    ps = list(map(int, input().split()))
    li = []
    ans = 0
    for i in ps:
        li.append(i)
        if sorted(li)[0] >= i:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    ps = list(map(int, input().split()))
    ans = 0
    minp = float("inf")
    for p in ps:
        minp = min(minp, p)
        if minp >= p:
            ans += 1

    print(ans)


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

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

ans = 0
for i in range(n - 1, -1, -1):
    tmp = AB[i][0] % AB[i][1]
    if tmp == 0:
        x = tmp
    else:
        x = AB[i][1] - tmp
    ans += x
    if i > 0:
        for j in range(i - 1, -1, -1):
            AB[j][0] += x
    #print(AB, x, ans)
        
print(ans)

### FIXED CODE ###

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

acc = 0
for i in range(n - 1, -1, -1):
    tmp = AB[i][0] % AB[i][1]
    if tmp == 0:
        x = tmp
    else:
        x = AB[i][1] - tmp
    acc += x
    if i > 0:
        AB[i - 1][0] += acc
    #print(AB, x, acc)
        
print(acc)
### BUGGY CODE ###

import numpy as np

N, W = map(int, input().split())

dp = np.ones([2, N * 10 ** 3 + 1], dtype=int) * float("inf")
dp[0][0], dp[1][0] = 0, 0
for i in range(N):
    index = i % 2
    w, v = map(int, input().split())
    for j in range(1, len(dp[0])):
        if j <= v:
            dp[index][j] = min(w, dp[index-1][j])
        else:
            dp[index][j] = min(w + dp[index-1][j-v], dp[index-1][j])

dp = np.minimum(dp[0], dp[1])
ans = 0
for i, w in enumerate(dp):
    if w <= W:
        ans = max(ans, i)
    else:
        break

print(ans)

### FIXED CODE ###

N, W = map(int, input().split())

dp = [[float("inf")] * (N * 10 ** 3 + 1) for _ in range(2)]
dp[0][0], dp[1][0] = 0, 0
for i in range(N):
    index = i % 2
    w, v = map(int, input().split())
    for j in range(1, len(dp[0])):
        if j <= v:
            dp[index][j] = min(w, dp[index-1][j])
        else:
            dp[index][j] = min(w + dp[index-1][j-v], dp[index-1][j])

ans = 0
for i, w in enumerate(dp[N % 2 - 1]):
    if w <= W:
        ans = max(ans, i)
    else:
        break

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

MOD = 10 ** 9 + 7
S = input()
l = len(S)

dp = [[0 for i in range(13)] for j in range(l + 5)]
dp[0][0] = 1

for i, s in enumerate(S):
    if s == '?':
        c = -1
    else:
        c = int(s)
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for n in range(13):
            dp[i + 1][(n * 10 + j) % 13] += dp[i][n]
        
        for m in range(13):
            dp[i + 1][m] %= MOD

print(dp[l][5])

### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()
l = len(S)

dp = [[0 for i in range(13)] for j in range(l + 5)]
dp[0][0] = 1

for i, s in enumerate(S):
    if s == '?':
        c = -1
    else:
        c = int(s)
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for n in range(13):
            dp[i + 1][(n * 10 + j) % 13] += dp[i][n]
        
        for m in range(13):
            dp[i + 1][m] %= MOD

print(dp[l][5])
### BUGGY CODE ###

N,A,B,K = map(int,input().split())
if A<B: A,B = B,A
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
#fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
#    fac_inv.append(inv(f))

mem = {}
def ncr(n,r):
    if (n,r) in mem:
        return mem[(n,r)]
    else:
        ret = mul(mul(fac[n], inv(fac[n-r])), inv(fac[r]))
        if len(mem) <= 10**5:
            mem[(n,r)] = ret
        return ret

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    for green in range(min(a,b) + 1):
        red = a - green
        blue = b - green
        if red + green + blue > N: continue
        tmp = 1
        tmp = mul(tmp, ncr(N, red+green+blue))
        tmp = mul(tmp, ncr(red+green+blue, green+blue))
        tmp = mul(tmp, ncr(green+blue, blue))
        ans += tmp
print(ans % MOD)


### FIXED CODE ###

N,A,B,K = map(int,input().split())
if A<B: A,B = B,A
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
    fac_inv.append(inv(f))

mem = [0] * (N+1)
def ncr(n,r):
    if mem[r] > 0:
        return mem[r]
    else:
        ret = mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])
        mem[r] = ret
        return ret

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    if b > N: continue
    ans += mul(ncr(N,a), ncr(N,b))
print(ans % MOD)
### BUGGY CODE ###

n = int(input())

a = []
for _ in range(n):
    p = int(input())
    if p not in a:
        a.append(p)
    else:
        a.remove(p)

print(len(a))


### FIXED CODE ###

n = int(input())

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

a = sorted(a)

ans = n
flag = 0
for i in range(1, n):
    if a[i] != a[i-1] or flag == 1:
        flag = 0
    else:
        flag = 1
        ans -= 2

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

def readinput():
    n,w=list(map(int,input().split()))
    wlist=[]
    vlist=[]
    for _ in range(n):
        ww,vv=list(map(int,input().split()))
        wlist.append(ww)
        vlist.append(vv)
    return n,w,wlist,vlist

def main(n,W,w,v):
    dp=[]
    for _ in range(n+1):
        dp.append([0]*(W+1))
    for i in range(1,n+1):
        for j in range(W+1):
            if j-w[i-1]>=0:
                dp[i][j]=max(dp[i-1][j-w[i-1]]+v[i-1], dp[i][j])
            dp[i][j]=max(dp[i-1][j], dp[i][j])
    return dp[n][W]

if __name__=='__main__':
    n,w,wlist,vlist=readinput()
    ans=main(n,w,wlist,vlist)
    print(ans)


### FIXED CODE ###

def readinput():
    n,w=list(map(int,input().split()))
    wlist=[]
    vlist=[]
    for _ in range(n):
        ww,vv=list(map(int,input().split()))
        wlist.append(ww)
        vlist.append(vv)
    return n,w,wlist,vlist

def main(n,W,w,v):
    dp=[]
    for _ in range(n+1):
        dp.append([0]*(W+1))
    for i in range(1,n+1):
        for j in range(W+1):
            if j-w[i-1]>=0:
                dp[i][j]=max(dp[i-1][j-w[i-1]]+v[i-1], dp[i][j])
            dp[i][j]=max(dp[i-1][j], dp[i][j])
    return dp[n][W]

if __name__=='__main__':
    n,w,wlist,vlist=readinput()
    ans=main(n,w,wlist,vlist)
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    N = int(input())
    C = list(input().strip())
    last = N
    ans = 0
    for i in range(N):
        if C[i] == 'W':
            for j in reversed(range(i+1, last)):
                if C[j] == 'R':
                    ans += 1
                    last = j
                    break
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    N = int(input())
    C = list(input().strip())
    last = N
    ans = 0
    for i in range(N):
        if C[i] == 'W':
            has_r = False
            for j in reversed(range(i+1, last)):
                if C[j] == 'R':
                    ans += 1
                    last = j
                    has_r = True
                    break
            if not has_r:
                break
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)
### BUGGY CODE ###

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

m = (n-1)/2

ls = [ans for _ in range(n)]

for i in range(n):
    for j in range(int(m)):
        ls[i] -= 2*(a[i+1+2*j])
    ls[i] = str(ls[i])
print(" ".join(ls))


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    s = sum(a)
    l1 = 0
    for i in range(n):
        if i%2==0:
            l1 += a[i]
        else:
            l1 -= a[i]
    print(l1,end=" ")
    for i in range(n-1):
        l1 = 2*a[i]-l1
        print(l1,end=" ")
    print()
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,a,b = [int(x) for x in input().rstrip().split()]
l=[]
n1=1
st=1
ans=0
ans1=1
for i in range(1,n+1):
    ans1 = ans1*((n-i+1)/i)
    if i==a or i==b:
        l.append(ans1)
        continue
    else:
        if n<(i/2):
            ans+=l[n-i]
        else:
            ans+=ans1
            l.append(ans1)
print(round(ans%(10**9+7)))


### FIXED CODE ###

mod=10**9+7
n,a,b=[int(x) for x in input().rstrip().split()]

def modpow(a,n):
  if n<1:
    return 1
  ans=modpow(a,n//2)
  ans=(ans*ans)%mod
  if n%2==1:
    ans*=a
  return ans%mod

def conb(n,i):
  inv,ans=1,1
  for j in range(1,i+1):
    ans=ans*(n-j+1)%mod
    inv=inv*j%mod
  return (ans*modpow(inv,mod-2))%mod

ans_n=pow(2,n,mod)-1
ans_a=conb(n,a)
ans_b=conb(n,b)

print((ans_n-ans_a-ans_b)%mod)
### BUGGY CODE ###

import itertools
s = input()
k = int(input())
ans = [[] for _ in range(k)]
x = list(set(s))
cnt = 0
for i in range(1,k+1):
    for v in itertools.product(x, repeat=i):
        y = "".join(v)
        if y in s and y not in ans[i-1]: 
            ans[i-1].append(y)
ans = list(itertools.chain.from_iterable(ans))
ans.sort()
print(ans[k-1])

### FIXED CODE ###

s = input()
k = int(input())
word = []
for i in range(len(s)):
  for j in range(i+1, i+k+1):
    word.append(s[i:j])
word = sorted(list(set(word)))
print(word[k-1])
### BUGGY CODE ###

S = input()
T = input()

Ls = len(S)
Lt = len(T)

dp = [[0] * (Lt + 1) for _ in range(Ls + 1)]

for i in range(Ls):
    for j in range(Lt):
        if S[i] == T[j]:
            # dp[i+1][j+1] = max(dp[i][j]+1, dp[i][j+1], dp[i+1][j])
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

match = []
now_row = Ls
now_column = Lt
while now_row > 0 and now_column > 0:
    if dp[now_row][now_column] == dp[now_row-1][now_column]:
        now_row -= 1
    elif dp[now_row][now_column] == dp[now_row][now_column-1]:
        now_column -= 1
    else:
        match.append(T[now_column-1])
        now_column -= 1
        now_row -= 1


match.reverse()
print("".join(match))

### FIXED CODE ###

S = input()
T = input()

Ls = len(S)
Lt = len(T)

dp = [[0] * (Lt + 1) for _ in range(Ls + 1)]

for i in range(Ls):
    for j in range(Lt):
        if S[i] == T[j]:
            # dp[i+1][j+1] = max(dp[i][j]+1, dp[i][j+1], dp[i+1][j])
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

match = []
now_row = Ls
now_column = Lt
while now_row > 0 and now_column > 0:
    if dp[now_row][now_column] == dp[now_row-1][now_column]:
        now_row -= 1
    elif dp[now_row][now_column] == dp[now_row][now_column-1]:
        now_column -= 1
    else:
        match.append(T[now_column-1])
        now_column -= 1
        now_row -= 1


match.reverse()
print("".join(match))
### BUGGY CODE ###

from collections import defaultdict

if __name__ == "__main__":
    n = int(input())
    s = input()

    rgb = defaultdict(list)

    for i in range(n):
        if s[i] == 'R':
            rgb[0].append(i)
        elif s[i] == 'G':
            rgb[1].append(i)
        else:
            rgb[2].append(i)

    ans = 0
    for r in rgb[0]:
        for g in rgb[1]:
            for b in rgb[2]:
                tmp = sorted([r, g, b])
                if tmp[1] - tmp[0] != tmp[2] - tmp[1]:
                    ans += 1

    print(ans)


### FIXED CODE ###

from collections import defaultdict

n = int(input())
s = input()

rgb = defaultdict(list)
blue = defaultdict(int)

for i in range(n):
    if s[i] == 'R':
        rgb[0].append(i)
    elif s[i] == 'G':
        rgb[1].append(i)
    else:
        blue[i] = i

ans = len(rgb[0]) * len(rgb[1]) * len(blue)

for r in rgb[0]:
    for g in rgb[1]:
        tmp = sorted([r, g])
        if tmp[0] - (tmp[1]-tmp[0]) in blue:
            ans -= 1
        if tmp[1] + (tmp[1]-tmp[0]) in blue:
            ans -= 1
        if (tmp[1]+tmp[0]) % 2 == 0 and (tmp[1]+tmp[0])//2 in blue:
            ans -= 1

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

import sys
import copy
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
a = []
mod = 10 ** 9 + 7
dp = [-1] * (2 ** N)
#dp[n]: 考慮する女の組みを二進数で表す。考慮する男は前から女の数番目まで。そのときの組み合わせ数。
dp[0] = 1
stack = [0]
next_stack = []

for _ in range(N):
	a.append(list(map(int, input().split())))
	
for i in range(N):
	while stack:
		n = stack.pop()
		tmp = n
		for j in range(N):
			r = tmp % 2
			if r == 0 and dp[n + (2 ** j)] == -1:
				next_stack.append(n + 2 ** j)
				dp[n + (2 ** j)] = a[i][j] * dp[n]
			elif r == 0 and dp[n + (2 ** j)] != -1:
				dp[n + (2 ** j)] += a[i][j] * dp[n]
				dp[n + (2 ** j)] %= mod
				
			tmp = tmp // 2
				
	stack = copy.copy(next_stack)
	next_stack = []
	
print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
mod = 10 ** 9 + 7
dp = [0] * (1 << N)
#dp[n] = c: 考慮する女の組を二進数で表す。iを考慮する女の数とすると、考慮する男は先頭からi番目まで。c: そのときの組み合わせ数。
dp[0] = 1
def bitcount(i): # i < 2^32
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
	
	
for n in range(1 << N):
	i = bitcount(n)
	c = dp[n]
	tmp = n
	tmp ^= (1 << N) - 1
	for j in range(N):
		r = 1 & tmp
		if r == 1 and a[i - 1][j] == 1:
			nc = dp[n + (1 << j)] + c 
			if nc >= mod:
				nc -= mod
			
			dp[n + (1 << j)] = nc
			
		tmp = tmp >> 1
		if tmp == 0:
			break
				
print(dp[-1])
### BUGGY CODE ###

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

goukei = 0
B = A
for i in range(N):
    a = A[0]
    del B[0]
    Bgoukei = sum(B)
    goukei = goukei + a*Bgoukei


k = 10**9 + 7
print(goukei%k)

### FIXED CODE ###

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

sumA = sum(A)
for i in range(N):
    a = A[i]
    sumA = sumA - a
    goukei = goukei + sumA*a

k = 10**9 + 7
print(goukei%k)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))
c,d,s = [0 for _ in range(n+1)],[0 for _ in range(n+1)],[0 for _ in range(n+1)]
for i in A:
    c[i] += 1
    d[c[i]] += 1
for i in range(1,n+1):
    s[i] = s[i-1]+d[i]
for i in range(1,n+1):
    l,u = 0,n+1
    while u-l > 1:
        mid = (l+u)//2
        if s[mid] >= i*mid:
            l = mid
        else:
            u = mid
    print(l)

### FIXED CODE ###

N = int(input())
 
A = list(map(int,input().split()))
 
dic = {}
 
for a in A:
 
    if a not in dic:
        dic[a] = 1
    else:
        dic[a] += 1
 
B = []
for i in dic:
    B.append(dic[i])
 
B.sort()
 
B_sub = B.copy()
 
for i in range(len(B)-1):
    B_sub[i+1] += B_sub[i] 
 
aind = N + 1
nind = len(B) - 1
 
#print (B,B_sub)
 
for i in range(N):
 
    i += 1
 
    while True:
 
        while nind > 0 and B[nind] > aind - 1:
 
          nind -= 1
 
        if i > len(B):
            print (0)
            break
 
        elif ((len(B) - 1) - nind ) * (aind-1) + B_sub[nind] >= (aind - 1) * i:
            print (aind - 1)
            break
 
        aind -= 1
### BUGGY CODE ###

N=input()
list=[]
a=[]
b=[]
c=[]
s=[]
t=0
for i in range(int(N)):
    list.append(input())
    # for l in range(len(a)):
    #     if(a[l]==list[i]):
    #         b[l]+=1
    #         t=1
    #         break
    # if t==0:
    #     a.append(list[i])
    #     b.append(1)
    # else:
    #     t=0
    if(list[i] in a):
        b[a.index(list[i])]+=1
    else:
        a.append(list[i])
        b.append(1)
m=max(b)
for i in range(len(a)):
    if b[i]==m:
        c.append(a[i])
s=sorted(c)
for i in range(len(s)):
    print(s[i])


    




### FIXED CODE ###

import collections
import sys
N=int(input())
S=[input() for i in range(N)]
c = collections.Counter(S).most_common()
c.sort()
c.sort(key=lambda c:c[1],reverse=True)
max_count=c[0][1]
for _ in c:
  if _[1]==max_count:
    print(_[0])
  else:
    sys.exit()
### BUGGY CODE ###

s=input()
K=int(input())
l=len(s)
d=[[s[i],l-i] for i in range(len(s))]
d=sorted(d)
h=dict()
ans=0
ca=d[0][0]   

for i in d:
    if(i[0]!=i[0][0]):
        break
    for j in range(1,max(i[1]+1,6)):
        if(s[l-i[1]:l-i[1]+j] not in h):
            ans+=1
            h.update({s[l-i[1]:l-i[1]+j]:1})
        else:
            pass


h=sorted(h)
print(h[K-1])

### FIXED CODE ###

s=input()
K=int(input())
l=len(s)
d=[[s[i],l-i] for i in range(len(s))]
d=sorted(d)
h=dict()
ans=0
ca=d[0][0]   

for i in d:
    if(i[0]!=i[0][0]):
        break
    z=min(i[1]+1,6)
    for j in range(1,z):
        if(s[l-i[1]:l-i[1]+j] not in h):
            ans+=1
            h.update({s[l-i[1]:l-i[1]+j]:1})
        else:
            pass


h=sorted(h)
print(h[K-1])