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

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N = _I()
A = [_I() for i in range(N)]

"""
何個色を使えば塗れるか
最も小さい数字からはじめれば？
最も左からはじめれば？
"""

res = [] 
for a in A:
    if len(res) == 0:
        res.append(a)
    else:
        if a <= res[0]:
            # 小さいので追加
            res = [a] + res
        else:
            # 入れ替え
            p = bisect.bisect_left(res, a)
            res[p-1] = a
print(len(res))


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N = _I()
A = [_I() for i in range(N)]

"""
何個色を使えば塗れるか
最も小さい数字からはじめれば？
最も左からはじめれば？
"""

def bisect(arr, val, cmp):
    l = -1
    r = len(arr)
    while r - l > 1:
        e = (l + r) >> 1
        if cmp(arr[e], val): l = e
        else: r = e
    return r

res = [] 
for a in A:
    #  print('a res', a, res)
    if len(res) == 0:
        res.append(a)
    else:
        if a <= res[-1]:
            # 小さいので追加
            res.append(a)
        else:
            # 入れ替え
            p = bisect(res, a, lambda x, y: x > y)
            if res[p] == a:
                p = bisect(res, a-1, lambda x, y: x > y)
                res[p] = a
            else:
                res[p] = a

print(len(res))
### BUGGY CODE ###



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

def cmp(a,b):
    if a == None:
        return True
    elif b == None:
        return False
    if len(a) > len(b):
        return False
    elif len(a) < len(b):
        return True
    else:
        if int(a) >= int(b):
            return False
        else:
            return True

dp = [None] * (N+10)
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = ""
for i in range(N+1):
    for s in A:
        if dp[i] == None and i!=0:
            continue
        ss = dp[i] + s
        if cmp(dp[i + l[int(s)]] , ss):
            dp[i + l[int(s)]] = ss
            

print(dp[N])


                





### FIXED CODE ###

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

dp = [-1 for i in range(N+10)]
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = 0
for i in range(N-1):
    for s in A:
        if dp[i] == -1 and i!=0:
            continue
        if dp[i + l[s]] < dp[i]*10+s:
            dp[i + l[s]] = dp[i]*10+s
print(dp[N])
### BUGGY CODE ###

import math
from functools import reduce

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

K=int(input())
sum=0


for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            sum+=ggcd(i,j,k)

print(sum)




### FIXED CODE ###

import math
K=int(input())
sum=0
for i in range(1,K+1):
    for j in range(1,K+1):
        if math.gcd(i, j)==1:
            sum+=K
        else:
            g=math.gcd(i, j)
            for k in range(1,K+1):
                sum += math.gcd(g,k)
print(sum)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
  b, c = map(int, input().split())
  a += [c] * b
a.sort()
print(sum(a[-n:]))

### FIXED CODE ###

from heapq import heappop, heappush

n, m = map(int, input().split())
a = list(map(int, input().split()))
q = []
for x in a:
  heappush(q, [-x, 1])
for i in range(m):
  b, c = map(int, input().split())
  heappush(q, [-c, b])
r = []
k = 0
while k < n:
  c, b = heappop(q)
  c = -c
  r += [c] * b
  k += b
print(sum(r[:n]))
### BUGGY CODE ###

N=int(input())
A=input().split()
S=[int(a) for a in A]
n=0
NN=[]
for b in S:
    if not b in NN:
        NN.append(b)
if len(NN)==N:
    print('YES')
else:
    print('NO')
    

### FIXED CODE ###

import collections
N=int(input())
A=input().split()
c = collections.Counter(A)
if N==len(c):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

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

mod = 10**9+7

fact = [1]
for i in range(1,5*10**5 + 1):
  fact.append((fact[-1]*i) % mod)
  
revfact = [1]
for i in range(1,5*10**5 + 1):
  revfact.append(pow(fact[i],mod-2,mod))

A = (fact[m]*revfact[n]*revfact[m-n]*fact[n]) % mod
B = 0
for i in range(n+1):
  tmp = (fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i]
  if i % 2 == 0:
    B += tmp
    B %= mod
  else:
    B -= tmp
    B %= mod
print((A*B) % mod)

### FIXED CODE ###

def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs
        

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

MOD = 10 ** 9 + 7
modFacts, invs = prepare(max(N, M))

ans = 0
for i in range(N + 1):
    Ti = (modFacts[N] * invs[i] * invs[N - i]) % MOD
    Ti *= (modFacts[M] * invs[M - i]) % MOD
    Ti %= MOD
    Ti *= pow(modFacts[M - i] * invs[(M - i) - (N - i)], 2, MOD)
    Ti %= MOD
    ans += pow(-1, i) * Ti
    ans %= MOD

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

from itertools import combinations


n = int(input())
a = list(map(int, input().split()))
ans = 0
a = [i for i in a if a.count(i) > 1]
b = [j for j in a if a.count(j) > 3]
a = set(a)
b = set(b)
a -= b
a = list(a)
b = list(b)
for v in combinations(a, 2):
    ans = max(ans, v[0] * v[1])
for s in range(len(b)):
    ans = max(ans, s ** 2)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
d = {}
for x in a:
    d[x] = d.get(x, 0) + 1
l = []
ans = 0
for num, cnt in sorted(d.items(), key=lambda x: x[0], reverse=True):
    if cnt > 3:
        if len(l) == 0:
            ans = num ** 2
            print(ans)
            exit()
        else:
            l.append(num)
            ans = l[0] * l[1]
            print(ans)
            exit()
    elif cnt > 1:
        l.append(num)
        if len(l) == 2:
            ans = l[0] * l[1]
            print(ans)
            exit()
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
  A[A.index(max(A))]=((max(A))//2)
 
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)

for i in range(M):
  x=heapq.heappop(A)
  y=(((-1)*x)//2)*(-1)  
  heapq.heappush(A,y)
print((-1)*sum(A))
### BUGGY CODE ###

numN = int(input())
input_line = input().split(' ')
brick = [int(i) for i in input_line]

bestSeq = 0

for i, b in enumerate(brick):
  seq = 0
  if b == 1:
    seq += 1
    cur = 2
    for c in brick[i:]:
      if c == cur:
        seq += 1
        cur += 1
    if seq > bestSeq:
      bestSeq = seq

if bestSeq == 0:
  print(-1)
else:
  print(numN - bestSeq)


### FIXED CODE ###

numN = int(input())
input_line = input().split(' ')
brick = [int(i) for i in input_line]

seq = 0

for i, b in enumerate(brick):
  if b == 1:
    seq += 1
    cur = 2
    for c in brick[i + 1:]:
      if c == cur:
        seq += 1
        cur += 1
    break

if seq == 0:
  print(-1)
else:
  print(numN - seq)
### BUGGY CODE ###

# 折れ線グラフで考えると
# ( : +1
# ) : -1
# 0で終わる
# 0未満にならない → 各文字列で最下点と和を利用
# 和がマイナスの部分と分けて、マイナス部分は反転して考える

n = int(input())
plus = []
minus = []
for i in range(n):
    min_v = 0
    sum_v = 0
    s = input()
    for j in range(len(s)):
        sum_v += 1 if s[j] == '(' else -1
        min_v = min(min_v, sum_v)
    if sum_v > 0:
        plus.append([min_v, sum_v])
    else:
        minus.append([min_v-sum_v, -sum_v])

plus.sort(key=lambda x:x[0], reverse=True)
minus.sort(key=lambda x:x[0], reverse=True)

sum_plus = 0
for min_v, sum_v in plus:
    if sum_plus + min_v < 0:
        print("No")
        exit()
    sum_plus += sum_v

sum_minus = 0
for min_v, sum_v in minus:
    if sum_minus + min_v < 0:
        print("No")
        exit()
    sum_minus += sum_v

if sum_plus == sum_minus:
    print("Yes")
else:
    print("No")





### FIXED CODE ###

# 折れ線グラフで考えると
# ( : +1
# ) : -1
# 0で終わる
# 0未満にならない → 各文字列で最下点と和を利用
# 和がマイナスの部分と分けて、マイナス部分は反転して考える

n = int(input())
plus = []
minus = []
for i in range(n):
    min_v = 0
    sum_v = 0
    s = input()
    for j in s:
        sum_v += 1 if j == '(' else -1
        min_v = min(min_v, sum_v)
    if sum_v > 0:
        plus.append((min_v, sum_v))
    else:
        minus.append((min_v-sum_v, -sum_v))

plus.sort(key=lambda x:x[0], reverse=True)
minus.sort(key=lambda x:x[0], reverse=True)

sum_plus = 0
for min_v, sum_v in plus:
    if sum_plus + min_v < 0:
        print("No")
        exit()
    sum_plus += sum_v

sum_minus = 0
for min_v, sum_v in minus:
    if sum_minus + min_v < 0:
        print("No")
        exit()
    sum_minus += sum_v

if sum_plus == sum_minus:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

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

a=0
for i in range(N+1):
  for j in range(N+1-i):
    for k in range(N+1-i-j):
      if 10000*i+5000*j+1000*k==Y and i+j+k==N:
        a=1
        print(str(i)+' '+str(j)+' '+str(k))
        exit()
    
print('-1 -1 -1')


### FIXED CODE ###

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

for i in range(N+1):
  for j in range(N+1-i):
    if 10000*i+5000*j+1000*(N-i-j)==Y:
      print(str(i)+' '+str(j)+' '+str(N-i-j))
      exit()
        
    
print('-1 -1 -1')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, k, q= map(int, input().split())
a=[k]*n
for i in range(q):
    p = int(input())
    for j in range(n):
        if (p-1) != j:
            a[j]-=1
for i in range(n):
    if a[i] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, k, q= map(int, input().split())
a=[k]*n
for i in range(q):
    p = int(input())
    a[p-1]+=1
for i in range(n):
    if a[i]-q > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import copy
N , C = map(int, input().split())
ds =[list(map(int, input().split())) for i in range(C)]
cs =[list(map(int, input().split())) for i in range(N)]
c0 = []
c1 = []
c2 = []
for i in range(N):
    for j in range(N):
        if (i+j) % 3 == 0:
            c0.append(cs[i][j])
        elif (i+j) % 3 == 1:
            c1.append(cs[i][j])
        else:
            c2.append(cs[i][j])
d = 10**9
l0 = len(c0)
l1 = len(c1)
l2 = len(c2)
for i in range(C):
    d0 = 0
    for l in range(l0):
         if (c0[l]-1) != i:
            d0 += ds[c0[l]-1][i]
    for j in range(C):
        if i == j:
            continue
        d1 = copy.copy(d0)
        for h in range(l1):
            if (c1[h]-1) != j:
                d1 += ds[c1[h]-1][j]
        for k in range(C):
            if i == k or j == k:
                continue
            d2 = copy.copy(d1)
            for l in range(l2):
                if (c2[l]-1) != k:
                    d2 += ds[c2[l]-1][k]
            if d > d2:
                d = d2
print(d)



### FIXED CODE ###

import collections
N , C = map(int, input().split())
ds =[list(map(int, input().split())) for i in range(C)]
cs =[list(map(int, input().split())) for i in range(N)]
c0 = collections.defaultdict(int)
c1 = collections.defaultdict(int)
c2 = collections.defaultdict(int)
for i in range(N):
    for j in range(N):
        if (i+j) % 3 == 0:
            c0[cs[i][j]] += 1
        elif (i+j) % 3 == 1:
            c1[cs[i][j]] += 1
        else:
            c2[cs[i][j]] += 1
            
d = 10**9
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if i == k or j == k:
                continue
            d0 = 0
            for l in c0:
                d0 += c0[l] * ds[l-1][i]
            for l in c1:
                d0 += c1[l] * ds[l-1][j]
            for l in c2:
                d0 += c2[l] * ds[l-1][k]
            if d > d0:
                d = d0
            
print(d)
### BUGGY CODE ###

import itertools

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

memory = []
for v in itertools.combinations(S, 3):
  if v not in memory:
    memory.append(v)
print(len(memory))

### FIXED CODE ###

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

ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    if S.find(num[0]) == -1:
        continue  # 1文字目が合っているかどうか
    S1 = S[S.find(num[0])+1:]
    if S1.find(num[1]) == -1:
        continue  # 2文字目が合っているかどうか
    S2 = S1[S1.find(num[1])+1:]
    if S2.find(num[2]) == -1:
        continue  # 3文字目が合っているかどうか
    ans += 1
print(ans)
### BUGGY CODE ###

import math

K = int(input())
ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans += math.gcd(a, math.gcd(b,c))
print(ans)


### FIXED CODE ###

import math
K = int(input())
count = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        tmp = math.gcd(i, j)
        for k in range(1, K+1):
            count += math.gcd(tmp, k)
print(count)
### BUGGY CODE ###

MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        ans += A[i] ^ A[j]
        ans %= MOD
print(ans)


### FIXED CODE ###

MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))

ans = 0
m = 1
for i in range(60):
    bits = sum((a & m for a in A))
    bits //= m
    ans += (bits * (N - bits) * m)
    ans %= MOD
    m <<= 1
print(ans % MOD)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

from collections import defaultdict

N = int(input())

S = 'RULD'

class Plane:
	__slots__ = ('x', 'y', 'd')

	def __init__(s, x, y, d):
		s.x, s.y, s.d = int(x), int(y), d

	def __lt__(s, o):
		return s.x < o.x

	def rotate(s):
		s.x, s.y = -s.y, s.x
		s.d = S[(S.index(s.d)+1)%4]


P = [Plane(*input().split()) for _ in range(N)]

INF = 10 ** 18
best = INF
for trial in range(4):
	P.sort()

	rdu, rdd, ry = (defaultdict(lambda: -INF) for _ in range(3))

	for p in P:
		if p.d == 'R':
			ry[p.y] = p.x
			rdu[p.y-p.x] = p.x
			rdd[p.y+p.x] = p.x
		elif p.d == 'L':
			if p.y in ry:
				best = min(best, (p.x - ry[p.y]) * 5)
		elif p.d == 'U':
			ty = p.x + p.y
			if ty in rdd:
				best = min(best, (p.x - rdd[ty]) * 10)
		elif p.d == 'D':
			ty = p.y - p.x
			if ty in rdu:
				best = min(best, (p.x - rdu[ty]) * 10)

	if trial != 3:
		for p in P: p.rotate()

print('SAFE' if best == INF else best)


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

from collections import defaultdict

N = int(input())

S = 'RULD'

class Plane:
	__slots__ = ('x', 'y', 'd')

	def __init__(s, x, y, d):
		s.x, s.y, s.d = int(x), int(y), d

	def __lt__(s, o):
		return s.x < o.x

	def rotate(s):
		s.x, s.y = -s.y, s.x
		s.d = S[(S.index(s.d)+1)%4]

P = []
for _ in range(N):
	x, y, d = input().split()
	P.append((int(x), int(y), d))

def rotate(s):
	return (-s[1], s[0], S[(S.index(s[2])+1)%4])

INF = 10 ** 18
best = INF
MAXC = 400000

for trial in range(4):
	P.sort(key=lambda v: v[0])

	rdu, rdd, ry = ([INF] * (2*MAXC+1) for _ in range(3))

	for (x, y, d) in P:
		if d == 'R':
			ry[y+MAXC] = x
			rdu[y-x+MAXC] = x
			rdd[y+x+MAXC] = x
		elif d == 'L':
			ty = y + MAXC
			if ry[ty] != INF:
				best = min(best, (x - ry[ty]) * 5)
		elif d == 'U':
			ty = x + y + MAXC
			if rdd[ty] != INF:
				best = min(best, (x - rdd[ty]) * 10)
		elif d == 'D':
			ty = y - x + MAXC
			if rdu[ty] != INF:
				best = min(best, (x - rdu[ty]) * 10)

	if trial != 3:
		P = [rotate(p) for p in P]

print('SAFE' if best == INF else best)
### BUGGY CODE ###

import bisect

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

A_pop = A.pop
A_insert = A.insert
for _ in range(M):
    ins = A_pop() // 2
    A_insert(bisect.bisect_left(A, ins), ins) 

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-n for n in A]
heapq.heapify(A)

for _ in range(M):
    high = -heapq.heappop(A)
    heapq.heappush(A, -(high//2))

print(-sum(A))
### BUGGY CODE ###

X, Y, Z, K = map( int, input().split())
A = list( map( int, input().split()))
B = list( map( int, input().split()))
C = list( map( int, input().split()))
A.sort( key=None, reverse = True)
B.sort( key=None, reverse = True)
C.sort( key=None, reverse = True)
AB = [0]*(X*Y)
for i in range(X):
    for j in range(Y):
        AB[i*Y+j] = A[i]+B[j]
AB.sort( key=None, reverse = True)
ABC = [0]*3000000
for i in range( min(X*Y, 3000)):
    for j in range(Z):
        ABC[i*Z + j] = AB[i]+C[j]
ABC.sort( key=None, reverse = True)
for i in range(K):
    print( ABC[i])

### FIXED CODE ###

X, Y, Z, K = map( int, input().split())
A = list( map( int, input().split()))
B = list( map( int, input().split()))
C = list( map( int, input().split()))
A.sort( key=None, reverse = True)
B.sort( key=None, reverse = True)
C.sort( key=None, reverse = True)
AB = [0]*(X*Y)
for i in range(X):
    for j in range(Y):
        AB[i*Y+j] = A[i]+B[j]
AB.sort( key=None, reverse = True)
ABC = [0]*3000000
for i in range( min(X*Y, 3000)):
    for j in range(Z):
        ABC[i*Z + j] = AB[i]+C[j]
ABC.sort( key=None, reverse = True)
for i in range(K):
    print( ABC[i])
### BUGGY CODE ###

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

cnt = 0
ans = 0
while cnt < M:
    min_cost = min(A)
    min_index = A.index(min_cost)
    if cnt + B[min_index] <= M:
        ans += min_cost * B[min_index]
        cnt += B[min_index]
    else:
        ans += min_cost * (M - cnt)
        cnt = M
    del A[min_index]
    del B[min_index]
    
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
AB = [0] * N
for i in range(N):
    AB[i] = list(map(int, input().split()))

AB = sorted(AB)
cnt = 0
ans = 0

for e in AB:
    if cnt + e[1] < M:
        ans += e[0] * e[1]
        cnt += e[1]
    else:
        ans += e[0] * (M - cnt) 
        break

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

l, r = map(int, input().split())
mod_min = 2100
for i in range(l,r):
    for j in range(i+1,r+1):
        m = (i*j) % 2019
        if m < mod_min:
            mod_min = m

print(mod_min)


### FIXED CODE ###

l, r = map(int, input().split())
mod = 2019
mod_min = 2019


for i in range(l,r):
    for j in range(i+1,r+1):
        m = (i * j) % mod
        if m < mod_min:
            mod_min = m
        if mod_min == 0:
            break
    if mod_min == 0:
        break

print(mod_min)
### BUGGY CODE ###

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


total = 0
for i in range(N):
    a = nums[i]
    b = sum(nums[i+1:])
    total += a*b

print(total % (1000000000+7))

### FIXED CODE ###

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

total = 0
sums = []
tmp = 0

for i in range(1, N):
    tmp += nums[N-i]
    sums.append(tmp)

for i in range(N-1):
    a = nums[i]
    b = sums[N-(i+2)]
    total += a*sums[N-(i+2)]

print(total % (1000000000+7))
### BUGGY CODE ###

import math
from collections import defaultdict


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    #
    # visited = [-1 for _ in range(N)]
    # visited[0] = 0
    #
    # current = 0
    # th = -1
    # per_loop = -1
    # for i in range(1, N):
    #     current = A[current] - 1
    #
    #     if visited[current] >= 0:
    #         # print(i, current, visited[current])
    #         per_loop = i - visited[current]
    #         th = visited[current]
    #         break
    #     else:
    #         visited[current] = i
    #
    # current = 0
    # # print(th, per_loop)
    # # print(th + (K - th) % per_loop)
    #
    # if th < 0:
    #     num_rep = K
    # else:
    #     num_rep = th + (K - th) % per_loop
    #
    # for i in range(num_rep):
    #     current = A[current] - 1
    #
    # print(current + 1)

    current = 0
    for i in range(K):
        current = A[current] - 1

    print(current + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
from collections import defaultdict


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    visited = [-1 for _ in range(N)]
    visited[0] = 0

    current = 0
    th = -1
    per_loop = -1
    for i in range(1, N+1):
        current = A[current] - 1

        if visited[current] >= 0:
            # print(i, current, visited[current])
            per_loop = i - visited[current]
            th = visited[current]
            break
        else:
            visited[current] = i

    current = 0
    # print(th, per_loop)

    if K < th:
        num_rep = K
    else:
        num_rep = th + (K - th) % per_loop

    for i in range(num_rep):
        current = A[current] - 1

    print(current + 1)


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

S = list(input())
Q = int(input())
R = 1
for _ in range(Q):
  inp = input()
  if inp[0]=='1':
    R *= -1
  else:
    o, f, c = inp.split()
    if f=='1' and R==-1 or f=='2' and R==1:
      S.append(c)
    else:
      S.insert(0, c)
S = S if R==1 else reversed(S)
S = ''.join(S)
print(S)

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
R = 1
Top = deque()
Top.append(S)
for _ in range(Q):
  inp = input()
  if inp[0]=='1':
    R *= -1
  else:
    o, f, c = inp.split()
    if f=='1' and R==-1 or f=='2' and R==1:
      Top.append(c)
    else:
      Top.appendleft(c)
S = ''.join(Top)
S = S if R==1 else S[::-1]
print(S)
### BUGGY CODE ###

s=input()
q=int(input())
keep=1
for i in range(q):
  lis=list(map(str,input().split()))
  if lis[0]=="1":
    keep*=-1
  elif lis[1]=="1":
    if keep==1:
      s=lis[2]+s
    else:
      s+=lis[2]
  else:
    if keep==1:
      s+=lis[2]
    else:
      s=lis[2]+s

if keep==1:
  print(s)
else:
  print(s[::-1])

### FIXED CODE ###

s=input()
q=int(input())
keep=1
mae=""
ato=""
for i in range(q):
  lis=list(map(str,input().split()))
  if lis[0]=="1":
    keep*=-1
  elif lis[1]=="1":
    if keep==1:
      mae=lis[2]+mae
    else:
      ato+=lis[2]
  else:
    if keep==1:
      ato+=lis[2]
    else:
      mae=lis[2]+mae

if keep==1:
  print(mae+s+ato)
else:
  print(ato[::-1]+s[::-1]+mae[::-1])
### BUGGY CODE ###

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

ans = 0
s = 0

def mod(x):
    return int(x % (1e+9 + 7))
 
for i in range(N):
    for j in range(N):
        if i<j:
            ans += A[i] * A[j]
print(mod(ans))
  

### FIXED CODE ###

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

ans = 0
s = 0

def mod(x):
    return int(x % int(1e+9 + 7))

for i in reversed(range(N-1)):
    s += A[i+1]
    s = mod(s)
    ans += A[i] * s

    ans = mod(ans) 

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

from fractions import gcd 
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
    ans=max(ans,reduce(gcd,a[:i]+a[i+1:]))
print(ans)

### FIXED CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
L=[0]
R=[0]
for i in range(n-1):
    L.append(gcd(L[i],a[i]))
    R.append(gcd(R[i],a[-1-i]))
MAX=0
for i in range(n):
    MAX=max(MAX,gcd(L[i],R[-1-i]))
print(MAX)