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

inf = float('inf')
N = int(input())
A = list(map(int, input().split()))
dp0=[[-inf]*(2+N//2) for _ in range(N+1)]
dp1=[[-inf]*(2+N//2) for _ in range(N+1)]
dp0[0][0] = 0

for i, x in enumerate(A):
    j = i // 2
    for n in (j, j + 1):
        dp0[i+1][n] = max(dp0[i][n], dp1[i][n])
        dp1[i+1][n] = dp0[i][n - 1] + x
    #print(dp0)
    #print(dp1)

print(max(dp0[N][N//2], dp1[N][N//2]))

### FIXED CODE ###

from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
dp=[defaultdict(lambda:-float('inf'))for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print(dp[-1][n//2])
### BUGGY CODE ###

N, M= map(int, input().split())
B=[]
for i in range(N):
    B.append([None]*2)
    l=input().split()
    B[i][0]=int(l[1])
    B[i][1]=int(l[0])
B.sort(reverse=True)
h=[0]*(M+1)
a=0
for i in range(N):
    for j in range(B[i][1],M+1):
        if h[j]==0:
            h[j]=1
            a+=B[i][0]
            break
print(a)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
l=[[] for i in range(10**5)]
for i in range(N):
    a,b=map(int,input().split())
    l[a-1].append(b)
h=[]
import heapq
a=0
for i in range(M):
    for j in l[i]:
        heapq.heappush(h,-j)
    if h:
        a-=heapq.heappop(h)
print(a)
### BUGGY CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)
 
n = int(input())
s = [int(input()) for i in range(n)]
ans = 0
 
def dfs(index, total):
    if index == n:
        if total % 10 != 0:
            global ans
            ans = max(ans, total)
        return
    if s[index] == 0:
        dfs(index + 1, total)
        return
    dfs(index + 1, total + s[index]) or dfs(index + 1, total)
 
dfs(0, 0)
print(ans)

### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)

INF = 1 << 60

# ここから書き始める
n = int(input())
s = [int(input()) for i in range(n)]
if sum(s) % 10 != 0:
    print(sum(s))
else:
    s.sort()
    for i in s:
        if i % 10 != 0:
            print(sum(s) - i)
            break
    else:
        print(0)
### BUGGY CODE ###

l, r = map(int, input().split())
ans = 2019
for i in range(l, r):
    for j in range(i + 1, r + 1):
        ans = min(ans, (i * j) % 2019)
print(ans)

### FIXED CODE ###

l, r = map(int, input().split())
ans = 2019
for i in range(l, min(l + 2019, r)):
    for j in range(i + 1, min(l + 2020, r + 1)):
        ans = min(ans, (i * j) % 2019)
print(ans)
### BUGGY CODE ###

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

mul = 1
for i in l:
    mul *= i
    
if(mul>10**18):print(-1)
else:print(mul)

### FIXED CODE ###

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

if( 0 in l):print(0)
else:
    
    mul = 1
    for i in l:
        mul *= i
        if(mul>=10**18):break
        
    if(mul>10**18):print(-1)
    else:print(mul)
### BUGGY CODE ###


import math
x=int(input())
serach_number = 200000


def sieve_of_eratosthenes(target):
    k=0
    dest = int(math.sqrt(target))
    target_list = list(range(2, target + 1))
    prime_list = []

    while True:
        num_min = min(target_list)
        if num_min >= dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)
        if num_min>=x:
            k=1
        if k==1:
            print(num_min)
            return
        i = 0

        while True:
            if i >= len(target_list):
                break
            elif target_list[i] % num_min == 0:
                target_list.pop(i)
            i += 1




sieve_of_eratosthenes(serach_number)


### FIXED CODE ###

import math
x=int(input())

serach_number = 100004

def sieve_of_eratosthenes(target, x):
    dest = int(math.sqrt(target))
    target_list = list(range(2, target + 1))
    prime_list = []

    while True:
        num_min = min(target_list)
        if num_min >= dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)


        i = 0

        while True:
            if i >= len(target_list):
                break
            elif target_list[i] % num_min == 0:
                target_list.pop(i)
            i += 1
    while True:
        if (x in prime_list) == True:
            print(x)
            break
        else:
            x +=1


sieve_of_eratosthenes(serach_number, x)
### BUGGY CODE ###

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

# 足場iに到るコスト
dp = [float('inf')] * n
dp[0] = 0

for i in range(1, n):
    for j in range(1, k + 1):
        if i < j:
            continue
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[-1])


### FIXED CODE ###

import sys


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


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

INF = 10 ** 9
dp = [INF] * n
dp[0] = 0
for i in range(n - 1):
    for j in range(1, k + 1):
        if j >= n - i:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(H[i + j] - H[i]))
print(dp[-1])
### BUGGY CODE ###

n, q = (int(i) for i in input().split())
ab = [[int(i) for i in input().split()] for _ in range(n-1)]
child_dict = {}
for i in range(n-2,-1,-1):
    cur = child_dict.get(ab[i][0],set({}))
    cur.add(ab[i][1])
    child_dict[ab[i][0]] = cur

for i, j in child_dict.items():
    for k in range(1,n+1):
        if k in child_dict.keys() and i in child_dict[k]:
            child_dict[k] = child_dict[k].union(j)


px = [[int(i) for i in input().split()] for _ in range(q)]

p = [0] * n

for j in range(q):
    rootidx = px[j][0]
    p[rootidx - 1] += px[j][1]
    if rootidx in child_dict.keys():
        for k in child_dict[rootidx]:
            p[k-1] += px[j][1]

print(*p)

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import deque
    N, Q = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    cost = [0]*N
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    for _ in range(Q):
        p, x = (int(i) for i in input().split())
        cost[p-1] += x

    def bfs(s):
        G_color = ['WHITE' for _ in range(len(G))]
        G_color[s] = 'GRAY'
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    cost[v] += cost[u]
                    Q.append(v)
            G_color[u] = 'BLACK'

    bfs(0)
    print(*cost)


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

from itertools import *

def sieve(n):
    a = range(n)
    a[:2] = None, None
    for i in range(2, n):
        if i ** 2 >= n: break
        if not a[i]: continue
        for i in range(i ** 2, n, i):
            a[i] = None
    return [v for v in a if v]

def isPrime(p):
    if p < 2:
        return False
    for i in count(2):
        if i * i > p:
            return True
        if p % i == 0:
            return False

a = sieve(50000)
while True:
    n = int(raw_input())
    if n == 0: break
    if n % 2 == 1:
        print 0
        continue
    ct = 0
    for v in a:
        if v > n / 2: break
        if isPrime(n - v):
            ct += 1
    print ct

### FIXED CODE ###

from itertools import *

def sieve(n):
    a = range(n)
    a[:2] = None, None
    for i in range(2, n):
        if i ** 2 >= n: break
        if not a[i]: continue
        for i in range(i ** 2, n, i):
            a[i] = None
    return a

b = sieve(50000)
a = [v for v in b if v]
while True:
    n = int(raw_input())
    if n == 0: break
    ct = 0
    for v in a:
        if v > n / 2: break
        if b[n - v]:
            ct += 1
    print ct
### BUGGY CODE ###

N, result = eval(input()), 1
List = list(map(int, input().split()))
for i in List:
    result *= i
print(result if result <= 10**18 else -1)

### FIXED CODE ###

n = int(input())
List = list(map(int, input().split()))
res = 1
if 0 in List:
    print(0)
    quit()
for x in List:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
### BUGGY CODE ###

n,k=map(int,input().split())
p=998244353
r=range
f=[1]
for i in r(k):f+=[(-~i*f[i])%p]
a=1<<~-k
for i in r(min(n-1,k)):a-=f[k-1]*pow(f[i]*f[k-1-i],-1,p)
print(a%p)

### FIXED CODE ###

n,k=map(int,input().split())
p=998244353
r=range
f=[1]
for i in r(k):f+=[-~i*f[i]%p]
a=0
for i in r(n-1,k):a+=f[k-1]*pow(f[i]*f[k-1-i],-1,p)
print(a%p)
### BUGGY CODE ###

n=int(input())

p=10**9+7

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

binA=[]
for i in range(n):
  binA.append(format(A[i],"060b"))

exp=[1]
for i in range(60):
  exp.append((exp[i]*2)%p)


ans=0
for i in range(60):
  num0=0
  num1=0
  for j in range(n):
    if binA[j][i]=="0":
      num0+=1
    else:
      num1+=1
  ans=(ans+num0*num1*exp[59-i])%p

print(ans)



  


### FIXED CODE ###

n=int(input())

p=10**9+7

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

binA=[]
for i in range(n):
  binA.append(format(A[i],"060b"))


lis=[0 for i in range(60)]

for binAi in binA:
  for j in range(60):
    lis[j]+=int(binAi[j])

binary=[0 for i in range(60)]

for i in range(n):
  for j in range(60):
    if binA[i][j]=="0":
      binary[j]+=lis[j]
    else:
      binary[j]+=n-lis[j]


binary[58]+=binary[59]//2
binary[59]=0


explis=[1]

for i in range(60):
  explis.append((explis[i]*2)%p)

ans=0
for i in range(59):
  ans=(ans+binary[i]*explis[58-i])%p

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

n=int(input())
S=input()
dictR=[]
dictG=[]
dictB=[]
r=0
g=0
b=0
for i in range(len(S)):
    if S[i]=="R":
        dictR.append(i)
        r+=1
    elif S[i]=="G":
        dictG.append(i)
        g+=1
    else:
        dictB.append(i)
        b+=1
sum=r*g*b
if sum!=0:
    for i in dictR:
        for j in dictG:
            for k in dictB:
                maxi=max(i,max(j,k))
                mini=min(i,min(j,k))
                medi=i+j+k-maxi-mini
                if maxi-medi==medi-mini:
                    sum-=1

print(sum)

### FIXED CODE ###

n=int(input())
S=input()
R={}
G={}
B={}
r=0
g=0
b=0
for i in range(n):
    if S[i] == 'R':
        R[i] = None
    elif S[i] == 'G':
        G[i] = None
    else:
        B[i] = None
cnt=len(R)*len(G)*len(B)
for b in B:
    for g in G:
        if (b+g)/2 in R:
            cnt-=1
for b in B:
    for r in R:
        if (b+r)/2 in G:
            cnt-=1
for r in R:
    for g in G:
        if (r+g)/2 in B:
            cnt-=1
print(cnt)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
flg=1
count=0
while(0==0):
    for i in A: #全て偶数か確かめる
        if i%2!=0:
            flg=0
            break
    if flg==1:
        for i in A:
            i=i%2
        count+=1
    else:
        break
print(count)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
 
flg=1
count=0
while True:
    for i in A: #全て偶数か確かめる
        if i%2==1:
            flg=0
            break

    if flg==1:
        for i in range(N):
            A[i]=A[i]//2
        count+=1
    else:
        break
print(count)
### BUGGY CODE ###

import collections
n = int(input())
li = list(map(int, input().split()))
def calc(a):
    return int(a*(a-1)*0.5)
for k in range(n):
	dic = collections.Counter(li)
	dic[li[k]] -=1
	data2 = map(calc, list(dic.values()))
	print(sum(data2))

### FIXED CODE ###

import collections
n = int(input())
a = map(int, input().split())
li = []
for i in a:
    li.append(i)
collections.Counter(li)
m = 0
dic = collections.Counter(li)
for i in dic.values():
    m += int(i*(i-1)*0.5)
for k in range(n):
      print(m-dic[li[k]]+1)
### BUGGY CODE ###

import sys

N = int(input())
button = [0]*N

for i in range(N):
    button[i] = int(input())-1
course = []
count, now = 0, 0

while not now in course:
    course.append(now)
    now = button[now]
    count += 1
    if now == 1:
        print(count)
        sys.exit()
print(-1)


### FIXED CODE ###

import sys

N = int(input())
button = [0]*N

for i in range(N):
    button[i] = int(input())-1
count, now = 0, 0

while count <= N:
    now = button[now]
    count += 1
    if now == 1:
        print(count)
        sys.exit()
print(-1)
### BUGGY CODE ###

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

Alist = sorted(Alist, reverse=True)
for i in range(M):
    Alist = [Alist[0]//2] + Alist[1:]
    Alist = sorted(Alist, reverse=True)

print(sum(Alist))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
Alist = list(map(int, input().split()))

q = []
for a in Alist:
    heapq.heappush(q, -a)

for i in range(M):
    m = heapq.heappop(q)
    heapq.heappush(q, -((-m)//2))

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

from math import sqrt

N = int(input())
for i in range(1, N+1):
    ans = 0
    if i <= 5:
        print(0)
        continue
    for j in range(1, int(sqrt(i-2))+1):
        for k in range(1, int(sqrt(i-2))+1):
            for l in range(1, int(sqrt(i-2))+1):
                if j**2+k**2+l**2+j*k+k*l+l*j==i:
                    ans += 1
    print(ans)

### FIXED CODE ###

from math import sqrt
N = int(input())
if N == 1:
    print(0)
    import sys
    sys.exit()
ans = [0] * (N+1)
x = int(sqrt(N-2))+1
for j in range(1, x):
    for k in range(1, x):
        for l in range(1, x):
            y = j**2+k**2+l**2+j*k+k*l+l*j
            if y <= N:
                ans[y] += 1
for n in ans[1:N+1]:
    print(n)
### BUGGY CODE ###

n = int(input())

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

for i in (a):
	b = max(a)
	if i ==b:
		print(sorted(a)[-2])
	else:
		print(b)

### FIXED CODE ###

n = int(input())

a = [int(input()) for l in range(n)]
b = max(a)
c = sorted(a)[-2]
for i in (a):
	if not i==b:
		print(b)
	else:
		print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

from bisect import bisect_left


def combination(n, r): #nCrを求める
    if n - r < r:
        r = n - r
    tmp = 1
    for i in range(n - r + 1, n + 1):
        tmp *= i
    for i in range(1, r + 1):
        tmp //= i
    return tmp



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

ans = 0
for a in A:
    tmp = bisect_left(A, a//2)

    aCb = combination(a, A[min(tmp, N - 1)])
    if ans < aCb and a > A[min(tmp, N - 1)]:
        a1 = a
        b1 = A[min(tmp, N - 1)]
        ans = aCb

    aCb = combination(a, A[max(0, tmp - 1)])
    if ans < aCb and a > A[max(0, tmp - 1)]:
        a1 = a
        b1 = A[max(0, tmp - 1)]
        ans = aCb

print (a1, b1)


### FIXED CODE ###

from bisect import bisect_left

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

def combination(n, r): #nCrを求める
    if n - r < r:
        r = n - r
    tmp = 1
    for i in range(n - r + 1, n + 1):
        tmp *= i
    for i in range(1, r + 1):
        tmp //= i
    return tmp
# print (a)

j = bisect_left(a, a[-1]//2)
# print (j)
tmp = abs(a[j]/a[-1] - 1/2)
ans1 = a[-1]
ans2 = a[j]
if j != 0:
    if tmp >= abs(a[j - 1]/a[-1] - 1/2):
        ans2 = a[j - 1]

print (ans1, ans2)
### BUGGY CODE ###

#import sys

#input = sys.stdin.readline

import heapq

def main():
#    h,w,a,b = map(int, input().split())
    a,b=map(int,input().split())
    i=2
    k=1
    c=max(a,b)
    count=1
    if a%2==0 and b%2==0:
        count+=1
    if a%3==0 and b%3==0:
        count+=1
    while i < c:
        i = 6 * k +1
        if a % i == 0 and b % i == 0:
            count += 1
        k += 1
    k = 1
    i = 2
    while i < c:
        i = 6 * k -1
        if a % i == 0 and b % i == 0:
            count += 1
        k += 1
    print(count)
#    for i in range(h):
#            print(aaa)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#import sys

#input = sys.stdin.readline

#import heapq
import math
import fractions

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True

def main():
#    h,w,a,b = map(int, input().split())
    a,b=map(int,input().split())
    m=4
    k=1

    count=1
    if a>b:
        a,b=b,a
    sosu=set()
    a = fractions.gcd(a,b)
    if a%2==0:
        sosu.add(2)
        while a%2==0:
            a//=2
    if a%3==0:
        sosu.add(3)
        while a%3==0:
            a//=3
#    print(d)
    c=math.sqrt(a)+1
 #   print(c)
    while m<=c and m!=1:
        if a%m==0:
            sosu.add(m)
            while a%m==0:
                a//=m

        m+=1
#    print(sosu)
    if sosu==set() and a!=1:
        sosu.add(a)
    if sosuhante(a) and a!=1:
        sosu.add(a)
#    print(sosu)
    count+=len(sosu)
    print(count)
#    for i in range(h):
#            print(aaa)

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

S = list(map(str,input()))

counter = 0
amari = [0]*2019

s = 0
for i in range(len(S)):
    if S[len(S)-i-1] == "0":
        continue
    else:
        s += int(S[len(S)-i-1]) * 10**i
        amari[s % 2019] += 1

for i in range(2019):
    counter += amari[i] * (amari[i]-1) / 2

counter += amari[0]

print(int(counter))

### FIXED CODE ###

S = list(map(int,input()))[::-1] #逆順

counter = 0
amari = [0]*2019
amari[0] = 1

s,d = 0,1

for i in S:
    s += i *d
    amari[s%2019] += 1
    d *= 10
    d %= 2019


for i in range(2019):
    counter += amari[i] * (amari[i]-1) / 2


print(int(counter))
### BUGGY CODE ###

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

dp = [123456789012] * (10**8 + 10)

dp[0] = 0
for i in range(h+1):
    if dp[i] == 123456789012:
        continue
    for j in range(n):
        dp[i+ab[j][0]] = min(dp[i+ab[j][0]],dp[i] + ab[j][1])
ans = 123456789012
for i in range(h,h+10000+2):
    ans = min(ans,dp[i])
print(ans)

### FIXED CODE ###

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

dp = [123456789012] * (10**8 + 10)

dp[0] = 0
for i in range(h+1):
    if dp[i] == 123456789012:
        continue
    for j in range(n):
        dp[i+ab[j][0]] = min(dp[i+ab[j][0]],dp[i] + ab[j][1])
ans = 123456789012
for i in range(h,h+10000+2):
    ans = min(ans,dp[i])
print(ans)
### BUGGY CODE ###

import sys
import math
from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

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

N = II()
S = input()

ans = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        if j < i:
            continue
        for k in range(1, N+1):
            if k < j:
                continue
            if j-i != k-j and S[i-1] != S[j-1] and S[i-1] != S[k-1] and S[k-1] != S[j-1]:
                    ans+=1
print(ans)

### FIXED CODE ###

import sys
import math
from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

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

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N-2):
  for j in range(i+1,N-1):
    k=2*j-i
    if k>=N:
      continue
    if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
      ans-=1
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(lambda x: int(x)-1, input().split()))
n = a[0]
his = [-1, n]
while True:
    n = a[n]
    if n in his:
        his.append(n)
        break
    his.append(n)
idx = his.index(his[-1])
loop = len(his[his.index(his[-1]):-1])
if len(his) > k:
    print(his[k]+1)
else:
    t = (k - idx) % loop
    g = his[idx:-1]
    print(g[t]+1)

### FIXED CODE ###

from sys import stdin

def main():
    n, k = map(int, stdin.readline().rstrip().split())
    a = [int(x)-1 for x in stdin.readline().rstrip().split()]
    n = a[0]
    his = [-1, n]
    f = his.append
    s = set()
    while True:
        n = a[n]
        if n in s:
            f(n)
            break
        f(n)
        s.add(n)
    idx = his.index(his[-1])
    loop = len(his[his.index(his[-1]):-1])
    if len(his) > k:
        print(his[k]+1)
    else:
        t = (k - idx) % loop
        g = his[idx:-1]
        print(g[t]+1)
main()
### BUGGY CODE ###

import itertools

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

for k in range(N):
  a=A[:k]+A[k+1:]
  a.sort()
  gr=itertools.groupby(a)
  s=0
  for _,group in gr:
    l=len(list(group))
    if l>=2:
      s+=int(l*(l-1)/2)
  print(s)

### FIXED CODE ###

import itertools

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

gr=itertools.groupby(sorted(A))
s=0
dic={}
for x,group in gr:
  l=len(list(group))
  if l >= 2:
    s+=l*(l-1)/2
  dic[x]=l

for k in range(N):
  l=dic[A[k]]
  if l >= 2:
    print(int(s-l*(l-1)/2+(l-1)*(l-2)/2))
  else:
    print(int(s))
### BUGGY CODE ###

n,m=map(int,input().split())
templ=[0]*m
temp=[]
tempb=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append([b,n])
  if b==n:
    tempb.append([a,b])
if len(temp)>=1 and ans==0:
  """
  c = [x for x in tempb if x in templ]
  if len(c)>=1:
    print("POSSIBLE")
  """
  for i in range(0,len(tempb)):
    if tempb[i] in temp:
      print("POSSIBLE")
      break
  else:
    print("IMPOSSIBLE")
else:
  print("IMPOSSIBLE")            
    

### FIXED CODE ###

n,m=map(int,input().split())
templ=[0]*m
temp=[]
tempb=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append(b)
  if b==n:
    tempb.append(a)
if len(temp)>=1 and ans==0:
  temp=set(temp)
  tempb=set(tempb)
  c = temp&tempb
  #c = [x for x in temp if x in tempb]
  if len(c)>=1:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")
  """
  for i in range(0,len(tempb)):
    if tempb[i] in temp:
      print("POSSIBLE")
      break
  """
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

import sys
from math import factorial, fabs
a, b = map(int, input().split())
try:
    if factorial(b)/factorial(a)==0:
        print("Zero")
        sys.exit()
except:
    if 0 in range(a, b+1):
        print("Zero")
        sys.exit()       
    c=0
x=True
if (fabs(a)-fabs(b))%2==0 and (b<0):
    x=False
a, b= fabs(a), fabs(b)
fin=int(factorial(b)/factorial(a))
if fin==0 and factorial(b)/factorial(a)!=0:
    fin=int(factorial(a)/factorial(b))
if x==False:
    fin*=-1
if fin==0:
    ans="Zero"
elif fin<0:
    ans="Negative"
else:
    ans="Positive"
print(ans)

### FIXED CODE ###

from math import fabs
a, b = map(int, input().split())
if a <= 0 and 0 <= b:
    print("Zero")
else:
    if a > 0:
        print("Positive")
    else:
        if (fabs(b - a) + 1) % 2 == 0:
            print("Positive")
        else:
            print("Negative")