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

import itertools

def checkXOR(a, b, c):
  if bin(b) == bin(a ^ c):
    return False
  else:
    return True
    
n = int(input())
a = list(map(int, input().split()))
#print(n, a)
all = list(itertools.permutations(a))
ff = False
for p in range(0, len(all)):
  for i in range(0, n):
    if i == 0:
      ff = checkXOR(all[p][n-1],all[p][i],all[p][i+1])
    elif i == n-1:
      ff = checkXOR(all[p][i-1],all[p][i],all[p][0])
    else:
      ff = checkXOR(all[p][i-1],all[p][i],all[p][i+1])
    if ff:
      break
  if ff:
    break

if ff:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

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

for i in range(n):
  aa = aa ^ a[i]

if aa == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

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

counts = [0 for _ in range(max(A)+1)]
for a in A:
  counts[a] += 1

integers = [1 for _ in range(max(A)+1)]
integers[0] = 0
integers[1] = 0
max_count = 0
for i in range(max(A)+1):
   if integers[i] >= 1:
    count = 0
    for j in range(i,max(A)+1,i):
      count += counts[j]
      integers[j] = 0
    max_count = max(max_count,count)

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

### FIXED CODE ###

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

def get_count(p):
  integers = [1 for _ in range(p+1)]
  integers[0] = 0
  integers[1] = 0
  counts = [0 for _ in range(p+1)]
  for a in A:
    counts[a] += 1
  answer = 0
  for i in range(p+1):
    if integers[i] >= 1:
      count = 0
      for j in range(i,p+1,i):
        count += counts[j]
        integers[j] = 0
      answer = max(answer,count)
  return answer

count = get_count(max(A))
if count == N:
  answer = 'not coprime'
elif count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)
### BUGGY CODE ###

N,M = map(int,input().split())
edge = []
p = 'POSSIBLE'
i = 'IMPOSSIBLE'
for _ in range(M):
    edge.append(list(map(int,input().split())))

from1 = []
is_reach = False
for go,to in sorted(edge,key=lambda x:x[0]):
    if go == 1:
        from1.append(to)
    else:
        if go in from1 and to == N:
            is_reach = True
            break
print(p if is_reach else i)

### FIXED CODE ###

N,M = map(int,input().split())
edge = []
p = 'POSSIBLE'
i = 'IMPOSSIBLE'
for _ in range(M):
    edge.append(tuple(map(int,input().split())))

from1 = set()
is_reach = False
for go,to in sorted(edge,key=lambda x:x[0]):
    if go == 1:
        from1.add(to)
    else:
        if go in from1 and to == N:
            is_reach = True
            break
print(p if is_reach else i)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd, numbers)
def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N = int(input())
    A = sorted([int(i) for i in input().split()])
    MOD = 10**9+7

    GCD = gcd_list(A)
    LCM = lcm_list(A)
    ans = 0
    if GCD != 1 and LCM == A[-1]:
        for i in range(N):
            ans = (ans + A[-1] // A[i]) % MOD
    else:
        for i in range(N):
            ans = (ans + LCM // A[i]) % MOD

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from fractions import gcd
from functools import reduce

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]
# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def gcd_list(numbers):
    return reduce(gcd, numbers)
def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N = int(input())
    A = sorted([int(i) for i in input().split()])
    MOD = 10**9+7

    GCD = gcd_list(A)
    LCM = lcm_list(A) % MOD
    ans = 0
    if GCD != 1 and LCM == A[-1]:
        for i in range(N):
            ans = (ans + A[-1] * mod_inv(A[i],MOD)) % MOD
    else:
        for i in range(N):
            ans = (ans + LCM * mod_inv(A[i],MOD)) % MOD

    print(ans)

if __name__ == "__main__":
    main()
### 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(int, input().split()))
a = [i*-1 for i in a]
heapq.heapify(a)
for i in range(m):
    x = ((-1) * heapq.heappop(a)) //2
    heapq.heappush(a, -x)
print(-sum(a))
### BUGGY CODE ###

S = list(input())
count=0
num=1
while True:
    num=0
    for i in range(len(S)-1):
        if S[i]=="B" and S[i+1]=="W":
            S[i]="W" 
            S[i+1]="B"
            count+=1
            num+=1
    if num==0:
        break
print(count)


### FIXED CODE ###

S =list(input())
count=0
w_count=0
for i in range(len(S)):
    if S[i]=="W":
        count+=i
        w_count+=1
print(int(count-w_count*(w_count-1)/2))
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    Q = int(input())
    K = list(map(int, input().split()))
    for k in K:
        d_cnt = 0
        m_cnt = 0
        dm_cnt = 0
        answer = 0
        for i in range(N):
            if i-k >= 0 and S[i-k] == "D":
                d_cnt -= 1
                dm_cnt -= m_cnt
            elif i-k >= 0 and S[i-k] == "M":
                m_cnt -= 1
            if S[i] == "D":
                d_cnt += 1
            elif S[i] == "M":
                m_cnt += 1
                dm_cnt += d_cnt
            elif S[i] == "C":
                answer += dm_cnt
        print(answer)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    Q = int(input())
    K = list(map(int, input().split()))
    for k in K:
        d_cnt = 0
        m_cnt = 0
        dm_cnt = 0
        answer = 0
        for i in range(N):
            c = S[i]
            if i-k >= 0:
                prevc = S[i-k]
                if prevc == "D":
                    d_cnt -= 1
                    dm_cnt -= m_cnt
                elif prevc == "M":
                    m_cnt -= 1
            if c == "D":
                d_cnt += 1
            elif c == "M":
                m_cnt += 1
                dm_cnt += d_cnt
            elif c == "C":
                answer += dm_cnt
        print(answer)


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

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N, K = map(int, input().split(" "))
	A = input().split(" ")
	A = [int(s) for s in A]
	
	DP = [100000000000000000000000000000000 for _ in range(N)]
	DP[0] = 0
	
	for i, val in enumerate(A):
		if i == 0:
			continue
		tmp = 100000000000000000000000000000000
		
		for j in range(K):
			index = j+1
			if i >= index:
				tmp1 = DP[i-index] + abs(A[i-index] - val)
				tmp = min(tmp, tmp1)
		DP[i] = min(DP[i], tmp)
		
	#print(DP)
	print(DP[N-1])
	
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

def main():
	N, K = map(int, input().split(" "))
	H = input().split(" ")
	H = [int(s) for s in H]
	
	DP = [-1 for _ in range(N)]
	DP[0] = 0
	
	for i in range(1, len(H)):
		paths = [DP[j] + abs(H[j] - H[i]) for j in range(max(0, i-K), i)]
		DP[i] = min(paths)
		
	print(DP[N-1])
		
if __name__ == "__main__":
	main()
### BUGGY CODE ###

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

list_a = list(set(a))

result = 0
for i in list_a:
    cnt = a.count(i)
    result = result + cnt if cnt < i else result + cnt - i

print(result)


### FIXED CODE ###

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

count_a = {}
for n in range(N):
    if a[n] in count_a.keys():
        count_a[a[n]] += 1
    else:
        count_a[a[n]] = 1

result = 0
for n in list(count_a.keys()):
    if count_a[n] != n:
        result = result + count_a[n] if count_a[n] < n else result + count_a[n] - n

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

inf = float('inf')
mod = 10**9+7
from itertools import product, permutations, combinations, combinations_with_replacement
import bisect

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]

d = {}
for i,i2 in enumerate(A):
    for j,j2 in enumerate(i2):
        d[j2] = (i+1,j+1)

def listsub(t1,t2):
    ret = []
    for n1,n2 in zip(t1,t2):
        ret.append(abs(n1-n2))
    return ret

for L, R in LR:
    result = 0
    for i in range(L, R, D):
        result += sum( listsub(d[i+D],d[i]) )
    print(result)

### FIXED CODE ###

inf = float('inf')
mod = 10**9+7
from itertools import product, permutations, combinations, combinations_with_replacement
import bisect

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]

d = {}
for i,i2 in enumerate(A):
    for j,j2 in enumerate(i2):
        d[j2] = (i+1,j+1)

def listsub(t1,t2):
    return (abs(t1[0]-t2[0]),abs(t1[1]-t2[1]))

dp = [0]*((H*W)+1)

for i in range(D+1,(H*W)+1):
    dp[i] = dp[i-D] + sum(listsub(d[i-D], d[i]))

for L, R in LR:
    print(dp[R] - dp[L])
### BUGGY CODE ###

import numpy as np
N = int(input())
a_s = input().split()
for i in range(N):
    a_s[i] = int(a_s[i])
a_s = np.array(a_s)

a_unique = np.unique(a_s)
a_counts = []
for i,a in enumerate(a_unique):
    a_counts.append(np.sum(a_s==a))
a_counts = np.array(a_counts)

ans = 0
for i in range(len(a_unique)):
    val = a_counts[i]
    if i>0:
        if a_unique[i-1]+1==a_unique[i]:
            val += a_counts[i-1]
            
    if i<len(a_unique)-1:
        if a_unique[i+1]-1==a_unique[i]:
            val += a_counts[i+1]
            
    if val > ans:
        ans = val
        
    if ans >= sum(a_counts[i:]):
        break
        
print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
a_s = input().split()
a_s = [int(a_s[i]) for i in range(N)]

c = Counter(a_s)
c = sorted(c.items(), key=lambda x:x[0])
a_unique, a_counts = zip(*c)

ans = 0
for i,a in enumerate(a_unique):
    val = a_counts[i]
    if (i>0):
        if (a_unique[i-1]+1==a):
            val += a_counts[i-1]
            
    if (i<len(a_unique)-1):
        if (a_unique[i+1]-1==a):
            val += a_counts[i+1]
    
    if val > ans:
        ans = val
        
print(ans)
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
for i in range(Q):
  a = ''
  ans = 0
  l, r = map(int,input().split())
  b = S[l-1:r]
  for j in b:
    if j == 'A' and len(a)==0:
      a += j
    if j == 'C' and len(a)!=0:
      ans += 1
      a = ''
  print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N, Q = map(int,input().split())
S = input()
nums = [0] * (N + 1)
for i in range(N):
  nums[i+1] = nums[i] + (1 if S[i:i+2]=='AC' else 0)
    
for j in range(Q):
  l, r = map(int,input().split())
  print(nums[r-1] - nums[l-1])
### BUGGY CODE ###

n,s=map(int,input().split())
a=list(map(int,input().split()))
d=[[0]*(s+1) for _ in range(n+1)]
d[0][0]=1
for j in range(0,s+1):
    for i in range(1,n+1):
        d[i][j]=2*d[i-1][j]
        if a[i-1]<=j:
            d[i][j]+=d[i-1][j-a[i-1]]
        d[i][j]=d[i][j]%998244353
print(d[n][s])

### FIXED CODE ###

n,s=map(int,input().split()) 
a=list(map(int,input().split()))
d=[[0]*(s+1) for _ in range(n+1)]
d[0][0]=1
for j in range(0,s+1):
    for i in range(1,n+1):
        d[i][j]=2*d[i-1][j]
        if a[i-1]<=j:
            d[i][j]+=d[i-1][j-a[i-1]]
        d[i][j]=d[i][j]%998244353
print(d[n][s])
### BUGGY CODE ###

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

ans = ""

Aians = sorted(enumerate(Ai), key = lambda x: x[-1])

for ansNum in Aians:
    ans = ans + str(ansNum[0] + 1) + " "

print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
Ai = list(map(int, input().split()))

#Aians = np.argsort(Ai) + 1
print(' '.join(map(str, np.argsort(Ai) + 1)))
### BUGGY CODE ###

N = input()
P_list = input().split()
# N = '5'
# P_list = '4 2 5 1 3'.split()
P_list = [int(i) for i in P_list]
length = len(P_list)
ans = length 
for i in range(1,length):

    for j  in range(i):
        if P_list[i] > P_list[j]:
            ans -= 1
            j= 0
            # print(P_list[i] , P_list[j],ans)
            break

print(ans)

### FIXED CODE ###

N = input()
P_list = input().split()
# N = '5'
# P_list = '4 2 5 1 3'.split()
P_list = [int(i) for i in P_list]
length = int(N)
ans = 0 
M = []
mini =-1
for i in range(length):
    # print(min(P_list[0:i+1]))
    if P_list[i] <mini or mini <0:
        mini = P_list[i]
    if mini == P_list[i]:
        ans +=1


    # if P_list[i]==min(P_list[0:i+1]):
    #     ans +=1
    
print(ans)
### BUGGY CODE ###

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

for _ in range(K):
    B = [0]*N
    for i, a in enumerate(A):
        bottom = i - a
        top = i + a + 1
        if bottom < 0:
            bottom = 0
        if top > N:
            top = N
        B[bottom:top] = list(map(lambda x: x+1, B[bottom:top]))
    A = B[:]

ans = ' '.join(list(map(str, A)))
print(ans)


### FIXED CODE ###

from numba import jit
import sys
input = sys.stdin.readline


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

    for _ in range(K):
        B = [0]*(N+1)
        for i, a in enumerate(A):
            B[max(0, i-a)] += 1
            B[min(N, i+a+1)] -= 1
        for j in range(1, N):
            B[j] += B[j-1]
        if A == B[:-1]:
            A = B[:-1]
            break
        A = B[:-1]

    ans = ' '.join(list(map(str, A)))
    print(ans)


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

N = int(input())
a=0
flag=0
for i in range(1,N+1):
    a=(a*10)+7
    p=a%N
    if p==0:
        print(i)
        flag=1
        break

if flag==0:
    print(-1)


### FIXED CODE ###

N = int(input())
a=0
flag=0
for i in range(1,N+1):
    a=(a*10+7)%N   
    if a==0:
        print(i)
        flag=1
        break

if flag==0:
    print(-1)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
X = []
C = [0] * N
for j in range(30):
    for i in range(N):
        X.append((i, j, A[i]>>j))
X = sorted(X, key = lambda x: -x[2])
ans = sum(A)
for i, j, x in X[:M]:
    if C[i] == j:
        C[i] += 1
        ans -= x - x//2
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
X = []
C = [0] * N
for j in range(30):
    for i in range(N):
        X.append(((A[i]>>j)<<24) + (i << 6) + j)
X = sorted(X)[::-1]
ans = sum(A)
for a in X[:M]:
    x, i, j = a >> 24, (a >> 6) % (1<<18), a % (1<<6)
    if C[i] == j:
        C[i] += 1
        ans -= x - x//2
print(ans)
### BUGGY CODE ###


import heapq
import collections
N =  int(input())
nums = list(map(int,input().split(" ")))
keta = [0 for _ in range(61)]
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = [1]
MOD = 10 ** 9 + 7
for i in range(60):
    temp = jijou[i] * 2
    temp%= MOD
    jijou.append(temp)

for num in nums:
    s = format(num,"b")
    l = len(s)
    for i in range(0,l):
        keta[i] += int(s[l - i - 1 ])
ans = 0
for j,num in  enumerate(nums[:-1]):
    s = format(num, "b")
    l = len(s)
    for i in range(0,61): #i →  2 ** i 乗 桁目に対応
        if l <= i:
            ans += (keta[i] * jijou[i]) % MOD
        else:
            if s[l - i - 1 ] == "0":
                ans += (keta[i] * jijou[i]) % MOD
            else:
#              (N - j + 1) - (keta[i] + 1 ) → 0が経っているところの個数
                ans += (( (N - j + 1) - (keta[i] + 1)  ) * ( jijou[i]) ) % MOD
                keta[i] -= 1
    ans %= MOD


print(ans)

### FIXED CODE ###


import heapq
import collections
import math
import sys
N =  int(input())
input = sys.stdin.readline
# num = a << b →  a  * (2 ** b)
# 1 << i → i桁目のマスク
# mask = 1 << i
# num = a << b
# num & mask


#
nums = list(map(int,input().split(" ")))
keta = [0] * 62
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = []
MOD = 10 ** 9 + 7


for num in nums:
    s = format(num,"b")
    l = len(s)

    for i in range(0,l):
        if s[l - i - 1 ] == "1":
            keta[i] += 1

ans = 0
temp = 1
for i in range(62):

    ans += ( keta[i] * (N - keta[i])) * temp
    ans %= MOD
    temp *= 2
    temp %= MOD
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
 
N, K = inpl()
A = sorted(inpl())
S = []
s = 0
for a in A:
    s += a
    S.append(s)

A = A[::-1]
DP = [True]+[False for _ in range(K-1)]

OK = [False for _ in range(N)]
 
for i, a in enumerate(A):
    DP1 = [False] * K
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP[-S[::-1][i]:], max(0, K-S[::-1][i])):
        if d:
            DP1[j] = True
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP1[j+a] = True
    DP = DP1 
if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
 
N, K = inpl()
A = sorted(inpl())
S = []
s = 0
for a in A:
    s += a
    S.append(s)

A = A[::-1]
DP = [True]+[False for _ in range(K-1)]

OK = [False for _ in range(N)]
 
for i, a in enumerate(A):
    DP1 = [False] * K
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP[-S[::-1][i]:], max(0, K-S[::-1][i])):
        if d:
            DP1[j] = True
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP1[j+a] = True
    DP = DP1 
if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))
### BUGGY CODE ###

N = int(input())
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1
tree = UnionFind(2*N)
for _ in range(N-1):
    u,v,w = map(int,input().split())
    if w%2==0:
        tree.unite(u,v)
        tree.unite(u+N,v+N)
    else:
        tree.unite(u,N+v)
        tree.unite(v,N+u)
print(0)
for i in range(2,N+1):
    if tree.find(1)==tree.find(i):
        print(0)
    else:
        print(1)

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    import heapq

    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        edges[u].append((v,w))
        edges[v].append((u,w))
    
    colors = [-1]*(N+1)
    que = [(0,1)]
    heapq.heapify(que)
    while que:
        c,n = heapq.heappop(que)
        if colors[n] == -1:
            colors[n] = c
            for nx,w in edges[n]:
                if w%2==0:
                    nxC = c
                else:
                    nxC = (c+1)%2
                heapq.heappush(que,(nxC,nx))

    for i in range(1,N+1):
        print(colors[i])

main()
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 1e+6
for n in range(N):
    score = len(list(filter(lambda x: x == 'W', S[:n]))) + len(list(filter(lambda x: x == 'E', S[n + 1:])))
    ans = min(ans, score)
print(ans)

### FIXED CODE ###

N = int(input())
S =input()
wn = [0] * (N + 1)
en = [0] * (N + 1)
for i in range(1, N + 1):
    if S[i - 1] == 'W':
        wn[i] = wn[i - 1] + 1
        en[i] = en[i - 1]
    else:
        wn[i] = wn[i - 1]
        en[i] = en[i - 1] + 1
ans = [wn[i] + en[N] - en[i + 1] for i in range(N)]
print(min(ans))
### BUGGY CODE ###

n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
dp = []
dp.append(1)
if 1 in a:
    dp.append(0)
else:
    dp.append(1)

for i in range(2,n+1):
    if i in a:
        dp.append(0)
    else:
        dp.append(dp[i-1] + dp[i-2])

print(dp[n]%(1000000007))

### FIXED CODE ###

n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
dp = []
dp.append(1)
if m == 0:
    a.append(-1)
j = 0
k = len(a)-1
if 1 == a[j]:
    dp.append(0)
    j = min(k,j+1)
else:
    dp.append(1)

for i in range(2,n+1):
    if i == a[j]:
        dp.append(0)
        j = min(k,j+1)
    else:
        dp.append(dp[i-1] + dp[i-2])

print(dp[n]%(1000000007))
### BUGGY CODE ###

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

for i in range(N):
  cnt = 0
  for j in range(N):
    for k in range(N):
      if i!=j and i!=k and j!=k and l[j]==l[k]:
        cnt += 1
  print(int(cnt/2))

### FIXED CODE ###

from collections import Counter

N = int(input())
l = list(map(int, input().split()))
set_l = set(l)

dictionary = Counter(l)
ll_dict = {}

cnt = 0
for k, v in dictionary.items():
  cnt += v*(v-1)//2

for n in range(N):
  print(cnt-(dictionary[l[n]]-1))
### BUGGY CODE ###

n=int(input())
a = list(map(int, input().split()))
x=[]
for i in range(1,n+1):
    for t in range(n):
        if a[t]==i:
            num=t+1
            print(num,end=' ')

### FIXED CODE ###

n=int(input())
a = list(map(int, input().split()))
x=[[] for _ in range(n)]
for i in range(n):
    x[a[i]-1] = i + 1
print(' '.join(map(str,x)))
### BUGGY CODE ###

n,m=map(int,input().split())
ass=[tuple(map(int,input().split())) for i in range(m)]

ass.sort(key = lambda x:x[1])
count = 0

while ass != []:
    count = count+1
    ref = ass[0]
    #print('ref',ref)
    ass.sort(key = lambda x:x[0])
    #print('sortedass',ass)
    index = next((x for x in list(enumerate(ass)) if x[1][0]>=ref[1]),(len(ass)+10,0) )[0]
    ass = ass[index::]
    ass.sort(key = lambda x:x[1])
    #print(index)
    #print(ass)

print(count)


### FIXED CODE ###

n,m=map(int,input().split())
ass=[tuple(map(int,input().split())) for i in range(m)]
ass.sort(key=lambda x:x[1])

acum = []

def ifsatisfied(ab):
    for x in acum:
        if ab[0]<x <=ab[1]:
            return(True)
    return(False)

for ab in ass:
    if not ifsatisfied(ab):
        acum.append(ab[1])

print(len(acum))
### BUGGY CODE ###

import numpy as np
n=int(input())
a=np.array([str(input()) for i in range(n)])
b=set(a)
b=[[i,0]for i in b]
lenb=range(len(b))
for i in lenb:
  for j in a:
    if j==b[i][0]:
      b[i][1]+=1
c=np.array([i[1] for i in b])
maxb=max(c)
b=sorted(b,key=lambda x:x[0])
for i in lenb:
  if b[i][1]==maxb:
    print(b[i][0])

### FIXED CODE ###

n=int(input())
a=[str(input()) for i in range(n)]
b={}
for i in a:
  if i in b:
    b[i]+=1
  else:
    b[i]=0
maxb=max(b.values())
b=sorted(b.items(),key=lambda x:x[0])
for i,j in b:
  if maxb==j:
    print(i)
### BUGGY CODE ###

import sys
def main():
  n = int(input())
  a = [0]*n
  for n in range(n):
    a[n]=int(sys.stdin.readline())-1
  sw = [0]
  while True:
    nextsw = a[sw[-1]]
    if nextsw == 1:
      print(len(sw))
      return
    if nextsw in sw:
      print(-1)
      return
    sw.append(nextsw)
if __name__ == '__main__':    
  main()

### FIXED CODE ###

import sys


def main():
    n = int(input())
    a = [0] * n
    for i in range(n):
        a[i] = int(sys.stdin.readline()) - 1
    sw = [False for _ in range(n)]
    nextsw = 0
    while True:
        if nextsw == 1:
            print(sw.count(True))
            return
        if sw[nextsw]:
            print(-1)
            return
        sw[nextsw] = True
        nextsw = a[nextsw]


if __name__ == '__main__':
    main()