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

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

def Lagrange_interpolation(X, Y, mod): # O(N**2)
    n = len(X) - 1
    for i in range(n+1):
        t = 1
        for j in range(n+1):
            if i != j:
                t = t * (X[i] - X[j]) % mod
        Y[i] = Y[i] * modinv(t, mod) % mod

    cur, nxt = 0, 1
    dp = [[0]*(n+2) for _ in range(2)]
    dp[0][0], dp[0][1] = -X[0], 1
    for i in range(1, n+1):
        for j in range(n+2):
            dp[nxt][j] = dp[cur][j] * -X[i] % mod
            if j:
                dp[nxt][j] = (dp[nxt][j] + dp[cur][j-1]) % mod
        cur, nxt = nxt, cur
    xinv = [modinv(v, mod) for v in X]
    ret = [0]*(n+1)
    for i in range(n+1):
        if Y[i] == 0:
            continue # 0割り対策
        if X[i] == 0:
            for j in range(n+1):
                ret[j] = (ret[j] + dp[cur][j+1] * Y[i]) % mod
        else:
            ret[0] = (ret[0] - dp[cur][0] * xinv[i] * Y[i]) % mod
            pre = -dp[cur][0] * xinv[i] % mod
            for j in range(1, n+1):
                ret[j] = (ret[j] - (dp[cur][j] - pre) * xinv[i] * Y[i]) % mod
                pre = (pre - dp[cur][j]) * xinv[i] % mod
    return ret

p = int(input())
a = list(map(int, input().split()))
x = list(range(p))
res = Lagrange_interpolation(x, a, p)
print(*res)

### FIXED CODE ###

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

def Lagrange_interpolation(X, Y, mod): # O(N**2)
    n = len(X) - 1
    for i in range(n+1):
        t = 1
        for j in range(n+1):
            if i != j:
                t = t * (X[i] - X[j]) % mod
        Y[i] = Y[i] * modinv(t, mod) % mod

    cur, nxt = 0, 1
    dp = [[0]*(n+2) for _ in range(2)]
    dp[0][0], dp[0][1] = -X[0], 1
    for i in range(1, n+1):
        for j in range(n+2):
            dp[nxt][j] = dp[cur][j] * -X[i] % mod
            if j:
                dp[nxt][j] = (dp[nxt][j] + dp[cur][j-1]) % mod
        cur, nxt = nxt, cur
    xinv = [modinv(v, mod) for v in X]
    ret = [0]*(n+1)
    for i in range(n+1):
        if Y[i] == 0:
            continue # 0割り対策
        if X[i] == 0:
            for j in range(n+1):
                ret[j] = (ret[j] + dp[cur][j+1] * Y[i]) % mod
        else:
            ret[0] = (ret[0] - dp[cur][0] * xinv[i] * Y[i]) % mod
            pre = -dp[cur][0] * xinv[i] % mod
            for j in range(1, n+1):
                ret[j] = (ret[j] - (dp[cur][j] - pre) * xinv[i] * Y[i]) % mod
                pre = (pre - dp[cur][j]) * xinv[i] % mod
    return ret

p = int(input())
a = list(map(int, input().split()))
x = list(range(p))
res = Lagrange_interpolation(x, a, p)
print(*res)
### BUGGY CODE ###


from collections import deque
s = deque(input())
q = int(input())
r = 0
b = ""
c = ""
for i in range(q):
    A = list(input().split())
    if A[0] == '1':
        s.reverse()
    else:
        if (A[1] == '1'):
            s.appendleft(A[2])
        else:
            s.append(A[2])
print("".join(s))


### FIXED CODE ###

from collections import deque

s = deque(input())

q = int(input())
r = 0
for _ in range(q):
    A = list(input().split())
    if A[0] == '1':
        r = (r + 1)%2
    else:
        if (A[1] == '1' and r % 2 == 0) or (A[1] == '2' and r % 2 == 1):
            s.appendleft(A[2])
        else:
            s.append(A[2])

if r == 1:
    s.reverse()
print("".join(s))
### BUGGY CODE ###


K,S = list(map(int, input().split()))
number_of_combinations = 0

for x in range(0,K+1):
    for y in range(0, K+1):
        for z in range(0,K+1):
            sum_of_integer = x + y + z
            if sum_of_integer == S:
                number_of_combinations += 1

print(number_of_combinations)

### FIXED CODE ###

K,S = list(map(int, input().split()))
number_of_combinations = 0
for x in range(0,K+1):
    for y in range(0, K+1):
        z = S-x-y
        if 0 <= z <= K:
            number_of_combinations += 1
print(number_of_combinations)
### BUGGY CODE ###

a = input()
b = len(a)
while ('01' in a) or ('10' in a):
    a = a.replace('01', '').replace('10', '')
print(b - len(a))

### FIXED CODE ###

a = input()
b = len(a)
print(b - abs(a.count('1')-a.count('0')))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(400000000)
n,k=map(int,input().split())
h=list(map(int,input().split()))
flog=[-1]*n
#初期値は0
def Num(dest):
    if flog[dest-1]!=-1:
        return flog[dest-1]
    if dest<k+2:
        res=abs(h[dest-1]-h[0])
        flog[dest-1]=res
        return res
    else:
        min=10**10
        for i in range(1,k+1):
            tmp=Num(dest-i)+abs(h[dest-1]-h[dest-i-1])
            if min>tmp:
                min=tmp
        flog[dest-1]=min
        return min
          

    
print(Num(n))

### FIXED CODE ###

import sys
sys.setrecursionlimit(400000000)
def main():
    n,k=map(int,input().split())
    h=tuple(map(int,input().split()))
    flog=[-1]*n
    for i in range(n):#dest=i 0が１
        if i<k+1:#0~k
            flog[i]=abs(h[i]-h[0])
        else:
            min=10**9
            for j in range(1,k+1):#1~k
                tmp=flog[i-j]+abs(h[i]-h[i-j])
                if tmp<min:
                    min=tmp
            flog[i]=min
    print(flog[n-1])
   # print(flog)
if __name__=="__main__":
    main()
### BUGGY CODE ###

import queue
n,m,k=map(int,input().split())
root=[[0]*n for i in range(n)]
for i in range(n):
    root[i][i]=2
#print(root)
for i in range(m):
    a,b=map(int,input().split())
   # print("berfot",root[a-1][b-1])
    root[a-1][b-1]=1
    root[b-1][a-1]=1
  #  print("after",root[a-1][b-1])
for i in range(k):
    a,b=map(int,input().split())
 #   print(a,b)
    root[a-1][b-1]=-float("inf")
    root[b-1][a-1]=-float("inf")
#print(root)
toVis=queue.Queue()
Visted=[]
OK={}

for i in range(n):
    Visted=[i]

    if i in OK.keys():
        continue
    toVis=queue.Queue()
    
    for j in range(len(root[i])):
        nex=root[i][j]
        if j not in Visted and nex==1:
            toVis.put(j)

    while toVis.empty()==False:
    
        now=toVis.get()
        if now in Visted:
            continue
     #   print("now :" ,now)
        Visted.append(now)
        for j in range(len(root[now])):
            nex=root[now][j]
            if nex==1 and j not in Visted:
      #          print("apend",nex)
                toVis.put(j)
   
    for j in range(len(Visted)):
        OK[Visted[j]]=Visted
#print(OK)
ans=[]
for i in range(n):
    num=0
    for value in OK[i]:
        if root[i][value]==0:
            num+=1
    ans.append(num)
print(" ".join(map(str,ans)))


    
        

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m,k=map(int,input().split())
uf=UnionFind(n)
block={}
for i in range(n):
    block[i]=[i]
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    block[a-1].append(b-1)
    block[b-1].append(a-1)
    
for i in range(k):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[]
#print(block)
for i in range(n):
    res=uf.size(i)
 #   print(res)
    for value in block[i]:
        if uf.same(value,i):
            res-=1
    ans.append(res)
print(*ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
z = 0
for j in range(n - 1):
    for i in range(j + 1):
        z += (a[i] * a[j + 1]) % 1000000007

a = z % 1000000007
print(a)

### FIXED CODE ###

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

z = 0
for i in range(n):
    z += a[i]
e = z % 2

y = (z ** 2) % 2000000014

x = 0
for j in range(n):
    x += a[j] ** 2
    x = x % 2000000014

w = int(((y - x) / 2) % 1000000007)
print(w)
### BUGGY CODE ###

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

mul = 1
for ele in a:
    mul *= ele
print(mul if mul <= 1e18 else -1)

### FIXED CODE ###

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

mul = 1
if 0 in set(a): mul = 0
else:
    iter = 0
    for i in range(n):
        mul *= a[i]
        if mul > 1e18:
            mul = -1
            break
print(mul)
### BUGGY CODE ###

# seishin.py
from collections import deque
N, M = map(int, input().split())
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())
    C[r].append((l, x))
dp = [[[0]*N for i in range(N)] for j in range(N)]

def check(k, *L):
    # r < g < b として扱う
    r, g, b = sorted(L)
    for l, x in C[k]:
        # 区間[l, k]内はx種類の色
        if x == 1:
            if not g < l:
                return 0
        elif x == 2:
            if not r < l or not l <= g:
                return 0
        else:
            if not l <= r:
                return 0
    return 1

MOD = 10**9 + 7

# 左からk個置いた時の各色の最右の位置を持ってメモ化dfs
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    res = memo[key] = (dfs(k+1, k+1, g, b) + dfs(k+1, r, k+1, b) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

### FIXED CODE ###

MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)


X = {(0, 0): 3}
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    Z = [0]*(N+1)
    if C[b+1]:
        if t1 <= b < s0:
            for (r, g), v in X.items():
                if t2 <= g < s1:
                    # r <- b+1
                    Z[g] += v
                if t2 <= r < s1:
                    # g <- b+1
                    Z[r] += v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [0]*(N+1)
        for (r, g), v in X.items():
            # r <- b+1
            Z[g] += v
            # g <- b+1
            Z[r] += v;
    for z, v in enumerate(Z):
        if v:
            X[z, b] = v % MOD
print(sum(X.values()) % MOD)
### BUGGY CODE ###

n, m = map(int, input().split())
AB = []
for i in range(n):
    a, b  = map(int, input().split())
    if a <= m:
        AB.append((a, b))
AB.sort(key=lambda ab: -ab[1])
counts = [0] * m
cands = [0] * m
total = 0
for a, b in AB:
    if a > m:
        continue
    for i in range(a - 1 + counts[a - 1], m):
        if cands[i] > 0:
            continue
        cands[i] = b
        counts[a - 1] += 1
        total += 1
        break
    if total == m:
        break
print(sum(cands))


### FIXED CODE ###

import heapq

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

cands = [[] for _ in range(m)]
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        cands[a - 1].append(-b)

heapq.heapify(cands[0])
total = 0
for i in range(m):
    if len(cands[0]) > 0:
        total -= heapq.heappop(cands[0])
    if i < m - 1:
        for c in cands[i + 1]:
            heapq.heappush(cands[0], c)

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

import queue
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
path = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    path[A-1].append(B-1)
    path[B-1].append(A-1)

parent = [-1] * (N)
parent[0] = 0

found = [False] * N
found[0] = True

depth = [10 ** 9] * N
depth[0] = 0

q = queue.Queue()
q.put(0)
while not q.empty():
    pos = q.get()
    possible_parent = []
    for next_room in path[pos]:
        if parent[next_room] == -1:
            if not found[next_room]:
                q.put(next_room)
                found[next_room] = True
                depth[next_room] = min(depth[next_room], depth[pos] + 1)
        else:
            possible_parent.append(next_room)

    for p1 in possible_parent:
        for p2 in possible_parent:
            if depth[p1] > depth[p2]:
                break
        else:
            parent[pos] = p1
            break

if -1 in parent:
    print("No")
else:
    print("Yes")
    for elem in parent[1:]:
        print(elem + 1)

### FIXED CODE ###

import queue
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
path = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    path[A-1].append(B-1)
    path[B-1].append(A-1)

parent = [-1] * (N)
parent[0] = 0

found = [False] * N
found[0] = True

depth = [10 ** 9] * N
depth[0] = 0

q = queue.Queue()
q.put(0)
while not q.empty():
    pos = q.get()
    possible_parent = []
    for next_room in path[pos]:
        if parent[next_room] == -1:
            if not found[next_room]:
                q.put(next_room)
                found[next_room] = True
                depth[next_room] = min(depth[next_room], depth[pos] + 1)
        else:
            possible_parent.append(next_room)

    for p1 in possible_parent:
        for p2 in possible_parent:
            if depth[p1] > depth[p2]:
                break
        else:
            parent[pos] = p1
            break

if -1 in parent:
    print("No")
else:
    print("Yes")
    for elem in parent[1:]:
        print(elem + 1)
### BUGGY CODE ###

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

for i in range(n):
    ans = a.count(i + 1)
    print(ans)


### FIXED CODE ###

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

ans = [0]* n

for i in a:
    ans[i - 1] += 1
    
for i in range(n):
    print(ans[i])
### BUGGY CODE ###


N = int(input())
Alist = list(map(int,input().split()))
import numpy as np
ans=np.zeros(N)

A2list=list(set(Alist))
#print(A2list)
for i in range(len(A2list)):

    ans[int(A2list[i])-1]=int(Alist.count(A2list[i]))

ans=map(int,ans.tolist())
print(*ans,sep="\n")

### FIXED CODE ###


N = int(input())
Alist = list(map(int,input().split()))#iの上司

result = [0]*N

for i in range(N-1):#最後の社員に部下いない
    result[Alist[i]-1] +=1#上司の順番の要素に+1

for i in range(N):
    print(result[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from bisect import bisect_left
N = int(input())
A = sorted(tuple(map(int, input().split())))
B = sorted(tuple(map(int, input().split())))
C = sorted(tuple(map(int, input().split())))

AB = [N for _ in range(N)]
BC = [N for _ in range(N)]
result = 0

j = 0
for i, a in enumerate(A):
    while a >= B[j]:
        AB[j] = i
        j += 1
        if j == N:
            break
    if j == N:
        break

sAB = []
for i in range(N):
    sAB.append(sum(AB[:i+1]))

j = 0
for i, b in enumerate(B):
    while b >= C[j]:
        BC[j] = i
        j += 1
        if j == N:
            break
    if j == N:
        break

for bc in BC:
    if bc:
        result += sAB[bc-1]
print(result)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from bisect import bisect_left, bisect
N = int(input())
A = sorted(tuple(map(int, input().split())))
B = sorted(tuple(map(int, input().split())))
C = sorted(tuple(map(int, input().split())))

AB = []
result = 0
 
for i in range(N):
    AB = bisect_left(A, B[i])
    BC = N - bisect(C, B[i])
    result += AB * BC

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

import numpy as np
from numba import jit
verbose = False

N, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split())), dtype=np.int64)

ul = np.ceil(np.sum(A)/(K))
ll= np.floor(np.max(A)/(K+1))

EPS = 1 / 10**6

@jit(nopython=True)
def cut(A, c, N):
    return (np.sum(np.ceil(A/c))-N)

c = np.ceil((ul+ll)/2)
mx = np.max(A)
while True:
    if ul-ll == 1:
        break
    nk = cut(A, c, N)
    if verbose:
        print('c:', c, 'nk:', nk, 'ul - ll:', ul, '/', ll)
    prev = c
    if nk  >K: # more cuts than target; larger logs can be made
        ll = c
        c = np.floor((ul + c)/2)
    else: #i.e. nk < K, less cuts than target
        ul = c
        c = np.ceil((c + ll)/2)
        
if cut(A, ll+EPS, N) >= K:
    print(np.min((np.max(A), int(ul))))
else:
    print(int(ll))
    


### FIXED CODE ###

import numpy as np
from numba import jit
import random
verbose = False
rand = False

if rand:
    N, K = random.choice(range(10)), random.choice(range(10))
    A = np.array(random.choices(range(10**9), k=N))
else:
    N, K = list(map(int, input().split()))
    A = np.array(list(map(int, input().split())), dtype=np.int64)

ul = np.ceil(np.sum(A)/(K+1))
ll= np.floor(np.max(A)/(K+1))

EPS = 1 / 10**6

@jit(nopython=True)
def cut(A, c, N):
    return (np.sum(np.ceil(A/c))-N)

c = np.ceil((ul+ll)/2)
mx = np.max(A)
while True:
    if ul-ll <= 1:
        break
    nk = cut(A, c, N)
    if verbose:
        print('c:', c, 'nk:', nk, 'ul - ll:', ul, '/', ll)
    prev = c
    if nk  >K: # more cuts than target; larger logs can be made
        ll = c
        c = np.floor((ul + c)/2)
    else: #i.e. nk < K, less cuts than target
        ul = c
        c = np.ceil((c + ll)/2)
        
if cut(A, ll+EPS, N) >= K:
    print(np.min((np.max(A), int(ul))))
else:
    print(int(ll))
### BUGGY CODE ###

n = int(input())
s = str(input())
r = []
g = []
def right(r,g):
    return (max(r,g)+(abs(r-g)))
def left(r,g):
    return (min(r,g)-(abs(r-g)))
def half(r,g):
    return ((r+g)//2)
for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
ans = len(r)*len(g)*(n-(len(r)+len(g)))
for i in range(len(r)):
    for j in range(len(g)):
        t = left(r[i],g[j])
        f = right(r[i],g[j])
        h = half(r[i],g[j])
        if f < n:
            if s[f] == "B":
                ans -= 1
        if 0 <= t:
            if s[t] == "B":
                ans -= 1
        if abs(r[i]-g[j])%2 == 0:
            if s[h] == "B":
                ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = str(input())
r = []
g = []
def right(r,g):
    return (max(r,g)+(abs(r-g)))
def left(r,g):
    return (min(r,g)-(abs(r-g)))
def half(r,g):
    return ((r+g)//2)
for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
ans = len(r)*len(g)*(n-(len(r)+len(g)))
for i in range(len(r)):
    for j in range(len(g)):
        t = left(r[i],g[j])
        f = right(r[i],g[j])
        h = half(r[i],g[j])
        if f < n:
            if s[f] == "B":
                ans -= 1
        if 0 <= t:
            if s[t] == "B":
                ans -= 1
        if abs(r[i]-g[j])%2 == 0:
            if s[h] == "B":
                ans -= 1
print(ans)
### BUGGY CODE ###

from sys import stdin
import bisect
n, m = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(x) for x in stdin.readline().rstrip().split()]
a.sort()
sum = 0
for i in range(m):
    harf = a[n-1] // 2
    a.remove(a[n-1])
    bisect.insort_left(a, harf)
for i in range(n):
    sum += a[i]
print(sum)


### FIXED CODE ###

from sys import stdin
import heapq
n, m = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(x) for x in stdin.readline().rstrip().split()]
a = [-1 * x for x in a]
heapq.heapify(a)
for i in range(m):
    harf = heapq.heappop(a)
    harf = ((harf*(-1))//2)*(-1)
    heapq.heappush(a,harf)
print(sum(a)*(-1))
### BUGGY CODE ###

N,W=map(int,input().split())
DP=[[0 for j in range(W+1)]for i in range(N+1)]
for i in range(N):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j>=w:
            DP[i+1][j]=max(DP[i][j-w]+v,DP[i][j])
        else:
            DP[i+1][j]=DP[i][j]
print(DP[N][W])

### FIXED CODE ###

N,W=map(int,input().split())
DP=[[0 for j in range(W+1)]for i in range(N+1)]
for i in range(N):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j>=w:
            DP[i+1][j]=max(DP[i][j-w]+v,DP[i][j])
        else:
            DP[i+1][j]=DP[i][j]
print(DP[N][W])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    
    BL = (300000).bit_length()
    WIDTH = pow(2, BL)
    BUFSIZE = pow(2, BL+1) - 1
    BASE = BUFSIZE - WIDTH
    
    buf = [0] * BUFSIZE
    
    def update(i, x):
        i += BASE
        buf[i] = x
        i = (i-1) // 2
        while i >= 0:
            v1 = buf[2*i+1]
            v2 = buf[2*i+2]
            buf[i] = v1 if v1 > v2 else v2
            i = (i-1) // 2
    
    # [q_left, q_right]
    def search(q_left, q_right):
        return _search(0, WIDTH, 0, q_left, q_right)
    
    def _search(l, width, i, q_left, q_right):
        if q_right < l or l + width - 1 < q_left:
            return 0
        if q_left <= l and l + width - 1 <= q_right:
            return buf[i]
        nwidth = width // 2
        c1 = _search(l, nwidth, 2*i+1, q_left, q_right)
        c2 = _search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
        return c1 if c1 > c2 else c2
    
    for _ in range(N):
        a = int(input().rstrip())
        maxlen = search(a-K, a+K)
        update(a, maxlen+1)
    print(search(0, 300000))

main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())

BL = (300001-1).bit_length()
WIDTH = pow(2, BL)
BUFSIZE = pow(2, BL+1) - 1
BASE = BUFSIZE - WIDTH
DEFAULT = 0

buf = [DEFAULT] * BUFSIZE

def update(i, x):
    i += BASE
    buf[i] = x
    i = (i-1) // 2
    while i >= 0:
        buf[i] = compare(buf[2*i+1], buf[2*i+2])
        i = (i-1) // 2

# [q_left, q_right]
def search(left, right):
    ansl = ansr = DEFAULT
    left += BASE
    right += BASE
    while left < right:
        if not (left & 1):
            ansl = compare(ansl, buf[left])
            left += 1
        if right & 1:
            ansr = compare(ansr, buf[right])
            right -= 1
        left = (left-1) // 2
        right = (right-1) // 2
    if left == right:
        ansl = compare(ansl, buf[left])
    return compare(ansl, ansr)

def compare(v1, v2):
    return v1 if v1 > v2 else v2

for _ in range(N):
    a = int(input().rstrip())
    maxlen = search(max(0, a-K), min(a+K, 300000))
    update(a, maxlen+1)
print(search(0, 300000))
### BUGGY CODE ###

N=int(input())
a=[-1]*(N+1)
b=[[] for i in range(N+1)]
for i in range(1,N+1):
  a[i]=int(input())
  b[a[i]].append(i)

prev=[2]  
count=0
button=2
while(button!=1):
  if len(b[button]) != 0:
    button = b[button].pop()
    if button not in prev:
      prev.append(button)
    else:
      button=prev[-1]
  else:
    prev.pop()
    if len(prev) == 0:
      print(-1)
      exit(0)
    button = prev[-1]
    continue

  
print(len(prev) - 1)

### FIXED CODE ###

N=int(input())
a=[-1]*(N+1)
for i in range(1,N+1):
  a[i]=int(input())
pos = 1
ans = 0
for _ in range(N):
  if pos == 2:
    print(ans)
    exit(0)
  pos = a[pos]
  ans += 1
  

print(- 1)