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

import sys

def way(moku, wa, cur):
    if wa==moku:
        return 1
    if cur == n or wa > moku:
        return 0
    re1 = way(moku, wa + ms[cur], cur + 1)
    re2 = way(moku, wa, cur + 1)
    return re1 + re2

n = int(sys.stdin.readline())
ms = []
for i in range(n):
    ms += [int(sys.stdin.readline())]

total=sum(ms)
dp=[0]*(total+1)
dp[0]=1
for m in ms:
    for i in range(total,m-1,-1):
        dp[i]=dp[i]*2+dp[i-m]
    for i in range(m):
        dp[i]*=2

border = (total + 1) // 2
yo=sum(dp[border:])*3
if total%2==0:
    yo-=way(total//2,0,0)*3
print((3**n-yo)%998244353)


### FIXED CODE ###

import numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 998244353
    n = int(input())
    mx = 90005
    dp = np.zeros(mx, dtype="i8")
    dp2 = np.zeros(mx, dtype="i8")
    dp[0] = 1
    dp2[0] = 1
    sum_a = 0
    for _ in range(n):
        a = int(input())
        sum_a += a
        dp[mx - 1:a - 1:-1] = dp[mx - 1:a - 1:-1] * 2 + dp[mx - a - 1::-1]
        dp[:a] *= 2
        dp %= md
        dp2[mx - 1:a - 1:-1] += dp2[mx - a - 1::-1]
        dp2 %= md
    ng = np.sum(dp[(sum_a + 1) // 2:]) - np.sum(dp2[(sum_a + 1) // 2:]) * 2 + 1
    ng %= md
    total = (pow(3, n, md) - 3 * pow(2, n, md) + 3) % md
    print((total - ng * 3) % md)
    # ALL-NG（NG…最大辺が周の半分以上になる）で求める
    # 最大辺を赤として、dp[r] 赤の和がrのパターンを求める
    # 「赤だけ」、「赤と他一色だけ」(両方dp2に含まれる)のパターンは除く必要がある
    # 赤の和が総和の半分以上になるパターンを考えるので、
    # 赤以外の色だけになるパターンは除く必要がない
    # その後、緑、青が最大の辺になる場合も考えて3倍

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

n,k = map(int,input().split())
s = []
for i in range(k):
  l,r = map(int,input().split())
  s.append((l,r))
MOD = 998244353

memo = [-1 for _ in range(n+1)]

def f(x):
  if x < 1:
    return 0
  if x == 1:
    return 1
  if memo[x] != -1:
    return memo[x]
  res = 0
  for l,r in s:
    for i in range(l,r+1):
      res += f(x-i)
      res %= MOD
  memo[x] = res
  return res

print(f(n))


### FIXED CODE ###

# D - Leaping Tak
n,k = map(int,input().split())
lr = [tuple(map(int,input().split())) for _ in range(k)]
MOD = 998244353

# 累積和を使ってもらうdpを効率よく実現する。

dp = [0 for _ in range(n+1)]
dpsum = [0 for _ in range(n+1)]
dp[1] = 1
dpsum[1] = 1
for i in range(2,n+1):
  for li,ri in lr:
    r = i-li
    if r < 1:
      continue
    l = max(i-ri-1,0)
    dp[i] += dpsum[r]-dpsum[l]
    dp[i] %= MOD
  dpsum[i] += dpsum[i-1]+dp[i]
  dpsum[i] %= MOD
print(dp[n])
### BUGGY CODE ###

def p_l():
    import sys
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    *a, = map(int, input().split())
    # dp[i][j]は区間[i,j]が残っているときの最大化
    dp = [[-1] * n for _ in range(n)]

    def dfs(l, r):
        if dp[l][r] != -1:
            return dp[l][r]
        if l == r:
            dp[l][r] = a[l]
            return a[l]
        dp[l][r] = max(a[l] - dfs(l + 1, r), a[r] - dfs(l, r - 1))
        return dp[l][r]

    dfs(0, n - 1)
    print(dp[0][n - 1])
    
p_l()

### FIXED CODE ###

def p_l_2():
    n = int(input())
    *a, = map(int, input().split())
    # dp[i][j]は区間[i,j]が残っているときの最大化
    dp = [[-1] * n for _ in range(n)]

    for i in range(n):
        for l in range(n - i):
            r = l + i
            if l == r:
                dp[l][r] = a[l]
            else:
                dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1])
    print(dp[0][n - 1])


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

l,r=map(int,input().split())

ans=2018
for i in range(l,r):
    for j in range(i+1,r+1):
        ch=(i*j)%2019
        ans=min(ch,ans)

print(ans)

### FIXED CODE ###

l,r=map(int,input().split())

ans=2018
for i in range(l,r):
    if i%2019==0:
        ans=0
        break
    if i%673==0:
        for j in range(i+1,r+1):
            if j%3==0:
                ans=0
                break
            ch=(i*j)%2019
            ans=min(ch,ans)
    if i%3==0:
        for j in range(i+1,r+1):
            if j%673==0:
                ans=0
                break
            ch=(i*j)%2019
            ans=min(ch,ans)

    if ans==0:
        break
    for j in range(i+1,r+1):
        ch=(i*j)%2019
        ans=min(ch,ans)
        if j%2019==0:
            ans=0
            break

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

import numpy as np
import math
from fractions import gcd
n,m = map(int,input().split())
a = np.array(input().split(),dtype=int)
a /= 2
a.sort()

def t_per2(k):
    num = 0
    while k%2 == 0:
        k = k//2
        num += 1
    return num

f = False
dcm = a[0]
t_2 = t_per2(a[0])
for i in a:
    dcm = (dcm*i)//gcd(dcm,i)
    if dcm > m or not t_per2(i) == t_2:
        f = True
        break

count = 0
if not f:
    count = math.ceil(int(m/dcm)/2)

print(count)


### FIXED CODE ###

import numpy as np
import math
from fractions import gcd
n,m = map(int,input().split())
a = np.array(input().split(),dtype=int)
a /= 2

def t_per2(k):
    return format(k,'b')[::-1].find('1')

f = False
dcm = a[0]
t_2 = t_per2(a[0])
for i in a:
    dcm = (dcm*i)//gcd(dcm,i)
    if dcm > m or not t_per2(i) == t_2:
        f = True
        break

count = 0
if not f:
    count = math.ceil(int(m/dcm)/2)

print(count)
### BUGGY CODE ###

N = int(input())
p = 1
for i in range(2, N + 1):
    p *= i
print(p % (10**9 + 7))

### FIXED CODE ###

N = int(input())
p = 1
for i in range(2, N + 1):
    p *= i
    p %= 10**9 + 7
print(p)
### BUGGY CODE ###

s = list(str(input()))
q = int(input())
for i in range (q):
    t = list(str(input()))
    if t[0] == '2':
        if t[2] == '1':
            S = [t[4]]
            S.extend(s)
            s = S
        else:
            s.append(t[4])
    else:
        s.reverse()
print(''.join(s))

### FIXED CODE ###

s = list(str(input()))
q = int(input())
f = []
b = []
cnt = 0
for i in range (q):
    t = list(str(input()))
    if t[0] == '2':
        if t[2] == '1':
            f.append(t[4])
        else:
            b.append(t[4])
    else:
        x = f
        y = b
        f = y
        b = x
        cnt += 1
f.reverse()
if cnt%2 != 0:
    s.reverse()
    
print(''.join(f) + ''.join(s) + ''.join(b))
### BUGGY CODE ###

import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def get_group(k):
        g = pd[k]
        if g < 0:
            return k
        gg = get_group(g)
        pd[k] = gg
        return gg

    def merge(j, k):
        g1 = get_group(j)
        g2 = get_group(k)
        if g1 != g2:
            d1 = -pd[g1]
            d2 = -pd[g2]
            if d2 > d1:
                g1, g2 = g2, g1
            pd[g2] = g1
            if d1 == d2:
                pd[g1] -= 1

    hp = []
    n, h, w = map(int, input().split())
    pd = [-1] * (h + w + 2)  # 親(parent)と深さ(depth)。0以上は親。負の場合、そのノードが根で絶対値が深さ。
    for _ in range(n):
        r, c, a = map(int, input().split())
        heappush(hp, [-a, r, h + c])
    cnt = h + w
    ans = 0
    while cnt and hp:
        a, r, c = heappop(hp)
        gr = get_group(r)
        gc = get_group(c)
        if gr + gc == 0: continue
        if gr == gc:
            pd[gr] = 0
        else:
            merge(gr, gc)
        ans -= a
        cnt -= 1
    print(ans)

main()


### FIXED CODE ###

import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def get_group(k):
        g = pd[k]
        if g < 0:
            return k
        gg = get_group(g)
        pd[k] = gg
        return gg

    def merge(j, k):
        g1 = get_group(j)
        g2 = get_group(k)
        if g1 != g2:
            d1 = -pd[g1]
            d2 = -pd[g2]
            if d2 > d1:
                g1, g2 = g2, g1
            pd[g2] = g1
            if d1 == d2:
                pd[g1] -= 1

    hp = []
    n, h, w = map(int, input().split())
    pd = [-1] * (h + w + 2)  # 親(parent)と深さ(depth)。0以上は親。負の場合、そのノードが根で絶対値が深さ。
    pd[0] = -(h + w + 2)
    for _ in range(n):
        r, c, a = map(int, input().split())
        heappush(hp, [-a, r, h + c])
    cnt = h + w
    ans = 0
    while cnt and hp:
        a, r, c = heappop(hp)
        gr = get_group(r)
        gc = get_group(c)
        if gr + gc == 0: continue
        if gr == gc:
            merge(gr, 0)
        else:
            merge(gr, gc)
        ans -= a
        cnt -= 1
    print(ans)

main()
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
 
A,V = input().rstrip().split()
B,W = input().rstrip().split()
T = int(input().rstrip())
A,V,B,W = int(A),int(V),int(B),int(W)
s=0
if V<=W:
  print('NO')
  s=1
else:
  for t in range(T):
    if B<A:
      A-=V
      B-=W
      if B>=A:
        print('YES')
        s=1
        break
    else:
      A+=V
      B+=W
      if B<=A:
        print('YES')
        s=1
        break
if s!=1:
  print('NO')

### FIXED CODE ###

from sys import stdin
input = stdin.readline
 
A,V = input().rstrip().split()
B,W = input().rstrip().split()
T = int(input().rstrip())
A,V,B,W = int(A),int(V),int(B),int(W)
s=0
L1=A-B
L2=B-A
S=V-W
if V<=W:
  print('NO')
  s=1
else:
    if B<A:
      if L1/S<=T:
        print('YES')
      else:print('NO')
    else:
      if L2/S<=T:
        print('YES')
      else:print('NO')
### BUGGY CODE ###

n = int(input())
s = str(input())
ans = 0
for i in range(1000):
    i = str(i).zfill(3)
    cursor = 0
    for j in range(n):
        if s[j] == i[cursor]:
            cursor += 1
            if cursor == 3:
                ans += 1
                break

print(ans)

### FIXED CODE ###

n = int(input())
s = str(input())
ans = 0
for i in range(1000):
    i = str(i).zfill(3)
    cursor = 0
    for j in range(n):
        if s[j] == i[cursor]:
            cursor += 1
            if cursor == 3:
                ans += 1
                break

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

def main():
    s=input()
    n=len(s)
    mod=10**9+7
    
    dp=[0]*13
    if s[-1]=="?":
        dp=[1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp[int(s[-1])]=1
    
    for i in range(1,n):
        imod=10**i %13
        ss0=s[n-i-1]
        if ss0!="?":
            dpnew = [ dp[(j-int(ss0)*imod)%13] %mod for j in range(13)]
        else:
            dpnew = [sum( dp[(j-k*imod)%13] for k in range(10)) %mod for j in range(13) ]
        dp=dpnew[:]
    print(dp[5])
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

#d
def main():
    s=input()
    n=len(s)
    mod=10**9+7
    
    if s[-1]=="?":
        dp=[1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp=[0]*13
        dp[int(s[-1])]=1
    
    for i in range(1,n):
        imod=10**(i %12)
        ss0=s[n-i-1]
        if ss0!="?":
            dpnew = [ dp[(j-int(ss0)*imod)%13] %mod for j in range(13)]
        else:
            dpnew = [sum( dp[(j-k*imod)%13] for k in range(10)) %mod for j in range(13) ]
        dp=dpnew[:]
    print(dp[5])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from bisect import bisect
D = range(10,61,10)
while True:
    n = input()
    if n == 0:
        break
    A = [0]*7
    for _ in xrange(n):
        A[bisect(D,input())] += 1
    print "\n".join(map(str,A))

### FIXED CODE ###

while True:
    n = input()
    if n == 0:
        break
    A = [0]*7
    for _ in xrange(n):
        A[min(int(raw_input())/10,6)] += 1
    print "\n".join(map(str,A))
### BUGGY CODE ###

S = input()[::-1]
 
## 余りを0~2018で総数保持
counts = [0]*2019
## 0桁の余りは0
counts[0] = 1
 
num, d = 0, 1
 
for c in S:
  ## 右から~桁の数字
  num += int(c) * d
  num %= 2019
  
  ## 次の桁
  d *= 10
  #d %= 2019
  
  counts[num] += 1
  
ans = 0
for cnt in counts:
  ## nC2の計算
  ans += cnt * (cnt-1) //2
  
print(ans)

### FIXED CODE ###

S = input()[::-1]
 
## 余りを0~2018で総数保持
counts = [0]*2019
## 0桁の余りは0
counts[0] = 1
 
num, d = 0, 1
 
for c in S:
  ## 右から~桁の数字
  num += int(c) * d
  num %= 2019
  
  ## 次の桁
  d *= 10
  d %= 2019
  
  counts[num] += 1
  
ans = 0
for cnt in counts:
  ## nC2の計算
  ans += cnt * (cnt-1) //2
  
print(ans)
### BUGGY CODE ###

import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))
 
Possible = True
NoNeed = 0
count = 0
while Possible and count < N * (N-1) // 2:
    for c in Comb:
        count += 1
        for i in range(N):
            if i!=c[0] and i!=c[1]:
                if A[c[0]][c[1]] < A[c[0]][i] + A[c[1]][i]:
                    continue
                elif A[c[0]][c[1]] == A[c[0]][i] + A[c[1]][i]:
                    NoNeed += A[c[0]][c[1]]
                    break
                else:
                    Possible = False
                    break
                    
if Possible:
    Total = 0
    for i in range(N):
        Total += sum(A[i])
    Total //= 2
    Total -= NoNeed
    print(Total)
else:
    print(-1)

### FIXED CODE ###

import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for i in range(k + 1):
    for j in range(k + 1):
        for l in range(k + 1):
            if i + j + l == s:
                count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for i in range(k + 1):
    for j in range(k + 1):
            if 0 <= s - i - j <= k:
                count += 1
print(count)
### BUGGY CODE ###

h,w,m=map(int,input().split())
lh=[0]*h
lw=[0]*w
l=[set() for _ in range(h)]
for i in range(m):
  h1,w1=map(int,input().split())
  l[h1-1].add(w1-1)
  lh[h1-1]+=1
  lw[w1-1]+=1
hmax=max(lh)

ans=0
lw2=[]
for i in range(h):
  if lh[i]==hmax:
    lw2=lw[:]
    for m in l[i]:
      lw2[m]-=1
    ans=max(ans,hmax+max(lw2))

print(ans)

### FIXED CODE ###

h,w,m=map(int,input().split())
lh=[0]*h
lw=[0]*w
l=set()
for i in range(m):
  h1,w1=input().split()
  l.add(h1+"_"+w1)
  lh[int(h1)-1]+=1
  lw[int(w1)-1]+=1

hmax=max(lh)
wmax=max(lw)
lh2=[]
lw2=[]
for i in range(h):
  if lh[i]==hmax:
    lh2.append(i)
for i in range(w):
  if lw[i]==wmax:
    for m in lh2:
      if str(m+1)+"_"+str(i+1) not in l:
        print(hmax+wmax)
        exit()      
print(hmax+wmax-1)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 1

for i in range(1,n):
    if p[i] == min(p[0:(i+1)]):
        count += 1
        
print(count)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 1
min_p = p[0]

for i in range(n):
    if min_p > p[i]:
        count += 1
        min_p = p[i]

print(count)
### BUGGY CODE ###

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
time = 0
cnt = 0
C = []
for x in range(N+1):
    L = K - sum(A[0:x])
    if L < 0:
        break
    y_max = 0
    for y in range(M+1):
        T = sum(B[0:y])
        if L >= T:
            y_max += 1
        else:
            break
    C.append(y_max - 1 + x)
print(max(C))

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for j in range(M):
    b.append(b[j] + B[j])
j = M
ans = []
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans.append(i + j)
ans_max = max(ans)
print(ans_max)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
# 幅優先探索（行きがけ）

import sys



def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N, K = LI()
    Aarray = LI()

    start = 1
    for i in range(K):
        start *= Aarray[i]

    for i in range(K, N):
        now = start/Aarray[i-K]*Aarray[i]
        if now > start:
            print("Yes")
        else:
            print("No")
        start = now


if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding: utf-8
# Your code here!
# 幅優先探索（行きがけ）

import sys


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N, K = LI()
    Aarray = LI()

    # start = 1
    # for i in range(K):
    #     start *= Aarray[i]

    # for i in range(K, N):
    #     now = start/Aarray[i-K]*Aarray[i]
    #     if now > start:
    #         print("Yes")
    #     else:
    #         print("No")
    #     start = now

    for i in range(K, N):
        now = Aarray[i-K]
        now2 = Aarray[i]
        if now2 > now:
            print("Yes")
        else:
            print("No")


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

from bisect import bisect_left

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

AB.sort(key=lambda x: x[1], reverse=True)

s = [i for i in range(1, M + 1)]
ret = 0
for a, b in AB :
    if a > s[-1] :
        continue
    
    a = bisect_left(s, a)
    s = s[:a] + s[a+1:]
    ret += b
    if not s :
        break
print(ret)

### FIXED CODE ###

from heapq import heappush, heappop

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

for _ in range(N) :
    a, b = map(int, input().split())
    if a <= M :
        AB[M-a].append(b)
    
q = []
for a in range(M+1) :
    for b in AB[a] :
        heappush(q, b)
        if len(q) > a + 1 :
            heappop(q)
            
print(sum(q))
### BUGGY CODE ###

from sys import stdin
N=int(input())
P=[int(x) for x in stdin.readline().rstrip().split()]
ans=0
flag=True
for i in range(N):
  for j in range(i):
    if(P[i]>P[j]):
      flag=False
      break
  if flag:ans+=1
  flag=True
print(ans)

### FIXED CODE ###

from sys import stdin
N=int(input())
P=[int(x) for x in stdin.readline().rstrip().split()]
ans=1
min=P[0]

for i in range(1,N):
  if(P[i] < min):
    ans+=1
    min=P[i]
print(ans)
### BUGGY CODE ###

#input
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

#output
import numpy as np
V = max(v)
INF = 10**6
dp = np.zeros((N+1, N*V+1), int)
dp[0] = INF
dp[0, 0] = 0

for i in range(N):
    for j in range(N*V+1):
        if j < v[i]:
            dp[i+1, j] = dp[i, j]
        else:
            dp[i+1, j] = min(dp[i, j], dp[i, j-v[i]] + w[i])

answer = 0
for i in range(N*V+1):
    if dp[N, i] <= W:
        answer = i

print(answer)

### FIXED CODE ###

#input
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

#output
import numpy as np
V = max(v)
INF = 10**10
dp = np.full((N+1, N*V+1), INF)
dp[0, 0] = 0

for i in range(N):
    dp[i+1, v[i]:] = np.minimum(dp[i, v[i]:], dp[i, :-v[i]]+w[i])
    dp[i+1, :v[i]] = dp[i, :v[i]]

answer = 0
for i in range(N*V+1):
    if dp[N, i] <= W:
        answer = i

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

import sys
N=int(input())
a=list(map(int, input().split()))
s=1
if 0 in a:
    print(0)
    sys.exit()
for i in a:
    s*=i
if s>10**18:
    print(-1)
    sys.exit()
print(s)

### FIXED CODE ###

import sys
N=int(input())
a=list(map(int, input().split()))
s=1
# aに0がある場合を省く
if 0 in a:
    print(0)
    sys.exit()
else:
# sが10^18になったら打ち切る
    for i in a:
        if s<10**18:
            s*=i
    if s>10**18:
        print(-1)
        sys.exit()
    print(s)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input())-1)
ans=1
i=0
while(1):
    if a[i]==1:
        print(ans)
        exit()
    elif a[i]==0 or a[i]==i:
        print(-1)
        exit()
    else:
        i=a[i]
        ans+=1

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input())-1)
ans=1
i=0
b=[]
while(1):
    if ans==n:
        print(-1)
        exit()
    elif a[i]==1:
        print(ans)
        exit()
    else:
        ans+=1
        i=a[i]
### BUGGY CODE ###

n = int(input())
A = sorted(list(map(int, input().split())))
c = 1
for i in range(n-1, 0, -1):
  if sum(A[:i]) >= (A[i]+1)//2:
    c += 1
  else:
    print(c)
    exit()
print(n)  

### FIXED CODE ###

n = int(input())
A = sorted(list(map(int, input().split())))
c = 1
sumA = sum(A)
for i in range(n-1, 0, -1):
  sumA -= A[i]
  if sumA*2 >= A[i]:
    c += 1
  else:
    print(c)
    exit()
print(n)
### BUGGY CODE ###

#
# abc055 b
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3"""
        output = """6"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """10"""
        output = """3628800"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """100000"""
        output = """457992974"""
        self.assertIO(input, output)


def resolve():
    N = int(input())

    p = 1
    for i in range(1, N+1):
        p *= i

    print(p % (10**9+7))


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

#
# abc055 b
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3"""
        output = """6"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """10"""
        output = """3628800"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """100000"""
        output = """457992974"""
        self.assertIO(input, output)


def resolve():
    N = int(input())

    ans = 1
    for i in range(1, N+1):
        ans *= i
        ans %= (10**9+7)

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()