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

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = [int(s) for s in input().split()]
    S.sort(reverse = True)

    result = []
    result.append(S[0])

    left = 1
    que = []
    que.append([])

    for i in range(N):
        for j in range(2**i):
            que.append([])
            for k in range(len(que[-2])):
                if result[j]<=que[-2][k]:
                    que[-1].append(que[-2][k])
                else:
                    result.append(que[-2][k])
                    que[-1].extend(que[-2][k+1:])
                    break
            else:
                for k in range(left,len(S)):
                    if result[j]<=S[k]:
                        que[-1].append(S[k])
                    else:
                        result.append(S[k])
                        left = k+1
                        break
                else:
                    print("No")
                    break
        else:
            continue
        break
    else:
        print("Yes")

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])


def main():
    N = I()
    S = sorted(LI(),reverse=True)

    flag = [True]*len(S)

    cur = []
    cur.append(S[0])
    flag[0] = False

    for i in range(N):
        nxt = [x for x in cur]
        j = 0

        for k in range(len(S)):
            if j >= len(cur):
                break
            elif flag[k] and S[k]<cur[j]:
                nxt.append(S[k])
                j+=1
                flag[k] = False
        if len(cur) != j:
            return("No")
        cur = sorted(nxt,reverse=True)
    return("Yes")

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

a, b, k = map(int, input().split())
for i in range(k):
    if a > 0:
        a -= 1
    elif b > 0:
        b -= 1
print(a, b, sep=' ')

### FIXED CODE ###

a, b, k = map(int, input().split())
b = b if a - k > 0 else b - (k - a) if b - (k - a) > 0 else 0
a = a - k if a - k > 0 else 0
print(a, b, sep=' ')
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]
ans=0
mod=10**9+7
for k in range(60):
    X=0
    Y=0
    for i in range(N):
        if A[i]^(2**k)>A[i]:
            X+=1
        else:
            Y+=1
    #print(X,Y)
    ans+=pow(2,k,mod)*(X*Y)
    ans%=mod
print(ans)


### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
ans=0
mod=10**9+7
for k in range(60):
    X=0
    Y=0
    for i in range(N):
        if A[i]^(2**k)>A[i]:
            X+=1
        else:
            Y+=1
    #print(X,Y)
    ans+=pow(2,k,mod)*(X*Y)
    ans%=mod
print(ans)
### BUGGY CODE ###

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

ans = 1
for i in a:
    ans *= i
if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

if 0 in a:
    print(0)
else:
    ans = 1
    for i in a:
        ans *= i
        if ans > 1000000000000000000:
            print(-1)
            exit()
    if ans > 1000000000000000000:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    S = [0] * (H*W + 1)

    dic = [(-1, -1) for i in range(H*W + 1)]
    for h in range(H):
        for w in range(W):
            dic[A[h][w]] = (h+1, w+1)

    for d in range(1, D+1):
        for idx in range(d, H*W+1):
            if H*W < idx+D:
                break
            i, j = dic[idx]
            x, y = dic[idx + D]
            S[idx+D] = abs(x - i) + abs(y - j) + S[idx]

    Q = int(input())
    for query in range(Q):
        le, ri = (int(i) for i in input().split())
        print(S[ri] - S[le])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    num_to_xy = {}
    d_sum = [[] for _ in range(D)]
    for h in range(H):
        for w in range(W):
            num_to_xy[A[h][w]] = (h+1, w+1)
            d_sum[A[h][w] % D].append((A[h][w]))
    for d in range(D):
        d_sum[d].sort()
        cur = []
        y, x = -1, -1
        j, i = -1, -1
        for i, a in enumerate(d_sum[d]):
            if i == 0:
                y, x = num_to_xy[a]
                continue
            j, i = num_to_xy[a]
            cur.append(abs(x - i) + abs(y - j))
            y, x = j, i
        s = [0] * (len(cur) + 1)
        for i in range(0, len(cur)):
            s[i+1] = s[i] + cur[i]
        d_sum[d] = s
    Q = int(input())
    for q in range(Q):
        le, ri = (int(i) for i in input().split())
        if le % D != 0:
            print(d_sum[le % D][(ri - le % D)//D] -
                  d_sum[le % D][(le - le % D)//D])
        else:
            print(d_sum[le % D][(ri - le % D)//D-1] -
                  d_sum[le % D][(le - le % D)//D-1])


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

N, M = map(int,input().split())
br = [list(map(int,input().split())) for i in range(M)]
br.sort(key=lambda x:x[1])
state = [1]*(N-1)
ans = 0

for i in range(M):
  if 0 in state[br[i][0]-1:br[i][1]-1]:
    continue
  else:
    state[br[i][1]-2] = 0
    ans += 1
print(ans)

### FIXED CODE ###

from operator import itemgetter
N, M = map(int, input().split())
table = []
for i in range(M):
  a,b = map(int, input().split())
  table.append((a,b))
t = 0
ans = 0
table.sort(key=itemgetter(1))
for a,b in table:
  if t < a:
    ans += 1
    t = b-1
print(ans)
### BUGGY CODE ###

from math import ceil,floor
import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
            
ans =P
first =1

for i in range(P,N):
    b = (V-((P-1)+(N-i)))
    target = A[i]+M
        
    if b<=0:
        if A[P-1]<=target:
            ans+=1
    else:
        if target<A[P-1]:
            break
        if first==1:
            Q = A[P-1:i]
        else:
            Q.append(A[i-1])
        
        Q_sum=sum(Q)
        len_Q=len(Q)
        if target*len_Q-Q_sum>=b*M:
            ans+=1
        else:
            break
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
           
right = P-1
left = N

while left - right !=1:
    
    i = (left+right)//2
    b = (V-((P-1)+(N-i)))
    target = A[i]+M

        
    if b<0:
        if A[P-1]<=target:
            right = i
        else:
            left = i
    else:
        if target<A[P-1]:
            left = i
        else:
            Q_sum=sum(A[P-1:i])
            len_Q =i-(P-1)
            if target*len_Q-Q_sum>=b*M:
                right = i
            else:
                left =i


print(right+1)
### BUGGY CODE ###

import sys
N,M=map(int,input().split())

graph=[]
for _ in range(N+1):
  graph.append([])

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)

vlist=graph[S]
t=0
while(True):
  t+=1
  if t>10**7:
    print(-1)
    sys.exit()
  
  nlist = []
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      for vv in graph[v]:
        nlist.append(vv)
      
  #print((t,nlist))
  vlist = nlist
  

### FIXED CODE ###

import sys
N,M=map(int,input().split())

graph=[]
for _ in range(N+1):
  graph.append([])

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  #if t>300003:
  #  print(-1)
  #  sys.exit()
  
  #nlist = []
  nset = set()
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      table[v][t%3]=True
      for vv in graph[v]:
        if not table[vv][(t+1)%3]:
          #nlist.append(vv)
          nset.add(vv)
          #table[vv][t%3]=True
          #print((vv,t%3))
      
  #print((t,nlist))
  #vlist = nlist
  vlist = list(nset)
  if len(vlist) == 0:
    print(-1)
    break
### BUGGY CODE ###

# AtCoder Grand Contest 033
# https://atcoder.jp/contests/agc033
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    H, W = i2nn()
    HW = H * W
    A = ii2ss(H)
    A = [[0 if s == '#' else HW for s in line] for line in A]
    for i in range(H):
        for j in range(1, W):
            A[i][j] = min(A[i][j-1]+1, A[i][j])
    for i in range(H):
        for j in range(W-2, -1, -1):
            A[i][j] = min(A[i][j+1]+1, A[i][j])
    for j in range(W):
        for i in range(1, H):
            A[i][j] = min(A[i-1][j]+1, A[i][j])
    for j in range(W):
        for i in range(H-2, -1, -1):
            A[i][j] = min(A[i+1][j]+1, A[i][j])
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] > ans:
                ans = A[i][j]
    print(ans)
 
main()

### FIXED CODE ###

# AtCoder Grand Contest 033
# https://atcoder.jp/contests/agc033
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

import datetime

def main():
    H, W = i2nn()
    HW = H * W
    A = ii2ss(H)
    A = [[0 if s == '#' else HW for s in line] for line in A]
    for i in range(H):
        for j in range(1, W):
            if A[i][j-1]+1 < A[i][j]:
                A[i][j] = A[i][j-1]+1
        for j in range(W-2, -1, -1):
            if A[i][j+1]+1 < A[i][j]:
                A[i][j] = A[i][j+1]+1
    for j in range(W):
        for i in range(1, H):
            if A[i-1][j]+1 < A[i][j]:
                A[i][j] = A[i-1][j]+1
        for i in range(H-2, -1, -1):
            if A[i+1][j]+1 < A[i][j]:
                A[i][j] = A[i+1][j]+1
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] > ans:
                ans = A[i][j]
    print(ans)

main()
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)] 

P = [10**12] * (N+1)
P[0] = 1
P[1] = 1
flg=False
for i in range(2, N+1):
    if i in a:
        continue
    if (i-1 not in a) and (i-2 not in a):
        P[i] = P[i-1] + P[i-2]
    elif i-1 not in a:
        P[i] = P[i-1]
    elif i-2 not in a:
        P[i] = P[i-2]
    else:
        flg=True
if flg:
    print(0)
else:
    print(P[N] % (10**9+7))

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)] )

P = [-1] * (N+1)
P[0] = 1
P[1] = 1
flg=False
MOD = 10**9 + 7
for i in range(2, N+1):
    if i-1 not in a:
        P[i] = P[i-1]
    if i-2 not in a:
        if P[i] != -1:
            P[i] += P[i-2] % MOD
        else:
            P[i] = P[i-2] % MOD
    if P[i]==-1:
        flg=True
        break
if flg:
    print(0)
else:
    print(P[N] % MOD)
### BUGGY CODE ###

from collections import defaultdict
import math

def f(n):
    yakusu = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yakusu.append(i)
            #if i != 1:
            #    break
            if i != n // i:
                yakusu.append(n // i)
    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
if tmp != 1:
    print('not coprime')
    exit()
A.sort(reverse=True)
for i in A:
    f(i)

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')


### FIXED CODE ###

from collections import defaultdict
import math

INF = 10 ** 6 + 1
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

def f(n):
    yakusu = []
    if is_prime[n]:
        yakusu.append(n)
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                yakusu.append(i)
                if i != n //i:
                    yakusu.append(n // i)
                break

    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
    f(A[i])

if tmp != 1:
    print('not coprime')
    exit()
eratorasu()
f(A[0])

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')
### BUGGY CODE ###

import sys
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
dic = {}
li = []
for i in range(m):
    p, y = na()
    li.append([p,y])
    if p not in dic.keys():
        dic[p] = [y]
    else:
        dic[p].append(y)
for v in dic.values():
    v.sort()
for p, y in li:
    for i, n in enumerate(dic[p]):
        if n == y:
            shi = str(p)
            num = str(i + 1)
            pad = 6 - len(shi)
            shi = '0' * pad + shi
            pad = 6 - len(num)
            num = '0' * pad + num
            print(shi + num)
            break

### FIXED CODE ###

import sys
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
buf = [None] * m
cnt = {k: [] for k in range(n + 1)}
for i in range(m):
    p, y = na()
    cnt[p].append((y, i))
for p, l in cnt.items():
    if not l:
        continue
    l.sort()
    for j, (y, i) in enumerate(l):
        buf[i] = '{:06d}{:06d}'.format(p, j + 1)

print('\n'.join(buf))
### BUGGY CODE ###

# coding: utf-8
N, M = map(int, input().split())
A = list(map(int, input().split()))
# A.sort(reverse=True)
for i in range(M):
    A.sort(reverse=True)
    A[0] //= 2
print(sum(A))

### FIXED CODE ###

# coding: utf-8
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: -1 * x, A))
# A.sort(reverse=True)
heapq.heapify(A)
for i in range(M):
    tmp = heapq.heappop(A)
    heapq.heappush(A, -1 * (-tmp // 2))
print(-sum(A))
### BUGGY CODE ###

import numpy as np
n=int(input())
for i in range(1,n+1):
    if np.sqrt(i)==int(np.sqrt(i)): a=i
print(a)

### FIXED CODE ###

import numpy as np
n=int(input())
for i in range(n,0,-1):
    if np.sqrt(i)==int(np.sqrt(i)):
        print(i)
        break
### BUGGY CODE ###

n = int(input())

def prime_decomposition(n):
    # 素因数分解
    if n < 2:
        return []
    prime_factors = []
    while n % 2 == 0:
        prime_factors.append(2)
        n >>= 1

    while n % 3 == 0:
        prime_factors.append(3)
        n //= 3

    a = 5
    b = 7
    while a ** 2 <= n:
        if n % a == 0:
            prime_factors.append(a)
            n //= a
        elif n % b == 0:
            prime_factors.append(b)
            n //= b
        else:
            a += 6
            b += 6
    if n > 1:
        prime_factors.append(n)
    return prime_factors

pfs = prime_decomposition(n)
pfs.reverse()

def ds(n):

    ret = 1
    while 10**ret <= n:
        ret += 1
    return ret

ln = len(pfs)
size = 2**ln

min_v = 100
for i in range(size):
    p = 1
    for j in range(ln):
        if 1<<j & i:
            p *= pfs[j]
    min_v = min(min_v, max(ds(p), ds(n//p)))
print(min_v)

### FIXED CODE ###

n = int(input())

def prime_decomposition(n):
    # 素因数分解
    if n < 2:
        return []
    prime_factors = []
    while n % 2 == 0:
        prime_factors.append(2)
        n >>= 1

    while n % 3 == 0:
        prime_factors.append(3)
        n //= 3

    a = 5
    b = 7
    while a ** 2 <= n:
        if n % a == 0:
            prime_factors.append(a)
            n //= a
        elif n % b == 0:
            prime_factors.append(b)
            n //= b
        else:
            a += 6
            b += 6
    if n > 1:
        prime_factors.append(n)
    return prime_factors

pfs = prime_decomposition(n)
pfs.reverse()

def ds(n):

    ret = 1
    while 10**ret <= n:
        ret += 1
    return ret

ln = len(pfs)
size = 2**ln

min_v = 100
for i in range(size):
    p = 1
    for j in range(ln):
        if 1<<j & i:
            p *= pfs[j]
    min_v = min(min_v, max(ds(p), ds(n//p)))
print(min_v)
### BUGGY CODE ###

from bisect import bisect_right as br
n,k=map(int,input().split())
b=[0]*(n+1)
def f(x):
    c=0
    while x>0:
        c+=b[x]
        x-=x&-x
    return c
def g(x,a):
    while x<n+1:
        b[x]+=a
        x+=x&-x
for i in range(n):
    g(i+1,int(input())-k)
c=[0]
d=0
for i in range(1,n+1):
    t=f(i)
    k=br(c,t)
    c.insert(k,f(i))
    d+=i-k
print((n*(n+1))//2-d)

### FIXED CODE ###

n,k=map(int,input().split())
b=[0]*(n+1)
for i in range(n):
    b[i+1]=b[i]+int(input())-k
a=sorted(set(b))
s={a[i-1]:i for i in range(1,len(a)+1)}
c=[]
for i in b:
    c.append(s[i])
b=[0]*(len(a)+1)
def f(x):
    c=0
    while x>0:
        c+=b[x]
        x-=x&-x
    return c
def g(x):
    while x<len(a)+1:
        b[x]+=1
        x+=x&-x
e=0
for i in range(n+1):
    e+=f(c[i])
    g(c[i])
print(e)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
A=[int(input())-1 for _ in range(n-1)]
C=[[] for _ in range(n)]
for i,a in enumerate(A):
    C[a].append(i+1)

def depth(k):
    l=len(C[k])
    if not l:
        return 0
    else:
        D=[]
        ret=-1
        for c in C[k]:
            D.append(depth(c))
        D.sort(reverse=True)
        for i,d in enumerate(D):
            ret=max(ret,d+i+1)
        return ret

print(depth(0))

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
A=[int(input())-1 for _ in range(n-1)]
C=[[] for _ in range(n)]
for i,a in enumerate(A):
    C[a].append(i+1)

def depth(k):
    l=len(C[k])
    if not l:
        return 0
    else:
        D=[]
        ret=-1
        for c in C[k]:
            D.append(depth(c))
        D.sort(reverse=True)
        for i,d in enumerate(D):
            ret=max(ret,d+i+1)
        return ret

print(depth(0))
### BUGGY CODE ###

n = int(input())
orig_n = n

res=[]
i = 2
while i <= (orig_n):
    if n % i == 0:
        n = n // i
        res.append(i)
        i = 1
    i += 1
print("{0}: {1}".format(orig_n, " ".join(map(str, res))))

### FIXED CODE ###

n = int(input())
orig_n = n
res=[]
i = 2
half_n = n // 2
root_n = int(n ** (1/2))
is_prime = True
while i <= (root_n):
    if orig_n % i == 0:
        is_prime = False
        break
    i += 1
if is_prime: res.append(orig_n)

while i <= half_n and not(is_prime):
    if n ==1:
        break
    if n % i == 0:
        n = n // i
        res.append(i)
        i = 1
    i += 1

print("{0}: {1}".format(orig_n, " ".join(map(str, res))))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

????????±?????¨??????
"""
import sys
from sys import stdin
input = stdin.readline


C = []
def calc_lcs4(X, Y):
    global C
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)

    C = [[0]*(n+1) for _ in range(m+1)] #  ???????????§??¨???

    max_lcs = 0

    pre_row = C[0]
    for i in range(1, m):
        row = C[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row

    print(max_lcs)


if __name__ == '__main__':
    num = int(input())

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        result = calc_lcs4(X, Y)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

最長共通部分列
"""


c = []
def prep_array(X, Y):
    global c
    """ 値が0の2次元配列を用意する。サイズは入力データの最大値を想定して縦横(1000+1)以上必要。 """
    # from array import array
    # c = [array('I', [0] * (len(X)+1)) for _ in range(len(Y)+1)]  #  arrayで用意
    c = [[0]*(len(Y)+2) for _ in range(len(X)+2)] #  リストで用意
    return c


def check_max(array):
    """ 2次元配列の中の最大の値を返す """
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    return max_lcs


def calc_lcs4(X, Y, c):
    """
    Y[j]のアクセス方法を変更
    リストの値を一旦変数に保存するように変更
    最長共通部分長を関数内で計算するように変更
    4/5 のテストデータを使用してプロファイリングすると実効時間は 5.6秒
    """
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0

    pre_row = c[0]
    for i in range(1, m):
        row = c[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row
    return max_lcs


if __name__ == '__main__':
    # データの入力
    num = int(input())
    #f = open('input.txt')
    #num = int(f.readline())

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        # 処理の実行
        result = calc_lcs4(X, Y, prep_array(X, Y))

        # 結果の表示
        print(result)
### BUGGY CODE ###

import fractions
from functools import reduce
N = int(input())
X = list(map(int, input().split()))

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
  
gcd = 1

for i in range(N):
  Y = X.pop(i)
  gcd_1 = gcd_list(X)
  gcd = max(int(gcd), int(gcd_1))
  X.insert(i,Y)
print(gcd)

### FIXED CODE ###

#解説の方針にしたがった
import fractions

N = int(input())
X = list(map(int, input().split()))
   
M = 1  
L = [0 for i in range(100004)] #L(0)=0
R = [0 for i in range(100004)]  #R(N+1) = 0

for i in range(N):
  L[i] = (fractions.gcd(L[i-1],X[i]))

for i in reversed(range(N)):
  #print(i)
  R[i] = (fractions.gcd(R[i+1],X[i]))
    
ans = 1

#print(L)
#print(R)
for i in range(N):
  ans = max(ans, fractions.gcd(L[i-1],R[i+1]))

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

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

count = 'YES'
for i in range(max(List)):
    List = list(map(lambda x:x-1, List))
    if List.count(0) == 2:
        count = 'NO'

print(count)

### FIXED CODE ###

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

List.sort()
count = 'YES'
for i in range(N-1):
    if List[i] == List[i+1]:
        count = 'NO'
        
print(count)
### BUGGY CODE ###

n=int(input())
if n<=3:
  print(1)
else:
  ans=4
  for i in range(2,int(n**(1/2)+1)):
    e=2
    while i**e<=n:
      if i**e>ans:
        ans=i**e
        e+=1
  print(ans)


### FIXED CODE ###

n=int(input())
if n<=3:
  print(1)
else:
  ans=[]
  for i in range(2,int(n**(1/2)+1)):
    e=2
    while i**e<=n:
      if i**(e+1)>n:
        ans.append(i**e)
        break
      e+=1
  print(max(ans))