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

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r)*math.factorial(r))

n,m=[int(i) for i in input().split()]
a1=[int(input()) for i in range(m)]
a1.append(n+1)
c1=1
a2=0
for i in a1:
    a3=i-1-a2
    c2=0
    for j in range(a3//2+1):
        c2+=combinations_count(a3-j,j)
    c1=(c1*c2)%(1000000007)
    a2=i+1
    if c1==0:
        break



print(c1)


### FIXED CODE ###

#フィボナッチ数列か…
#c問題も解けないのか…
#典型問題なんだろうな
#踏めない段の分は除いて考えれば良い
n,m=input().split()
n,m=int(n),int(m)
ax=[1]*(n+1)
for i in range(m):
    ax[int(input())]=0
bx=[1,1]
for i in range(2,n+1):
    if ax[i-1]==1:
        f1=bx[i-1]
    else:
        f1=0
    if ax[i-2]==1:
        f2=bx[i-2]
    else:
        f2=0
    bx.append((f1+f2)%(10**9+7))

print(bx[n])
### BUGGY CODE ###

import sys
f=sys.stdin
ans=1
n=int(f.readline().strip())
prime=[]
# Start from where n is equal to 2
for _ in range(1,n):
    number_of_multiply=[]
    num_of_divisor=1
    tmp=_+1
    for __ in prime:
        cnt=0
        if tmp<=1:
            break
        while (tmp%__)==0:
            cnt+=1;tmp//=__;
        if cnt>0:
            num_of_divisor*=cnt+1
    if num_of_divisor==1:
        prime.append(_+1)
        ans+=(_+1)*2
    else:
        ans+=(_+1)*num_of_divisor
print(ans)

### FIXED CODE ###

import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202006_5th/D_input.txt")
else:
    f=sys.stdin
ans_sum=0
n=int(f.readline().strip())
for _ in range(1,n+1):
    num=n//_
    ans_sum+=_*((num*(num+1))//2)
print(ans_sum)
### BUGGY CODE ###

s = input()
x, y = map(int, input().split())

XY = [[], []]
b = 0
renzoku = 0
for i in range(len(s)) :
    if s[i] == "T" :
        b = (b+1) % 2
        renzoku = 0
    else :
        if renzoku == 0 :
            XY[b].append(1)
            renzoku = 1
        else :
            XY[b][-1] += 1


#print(XY)

g = 10000

X = [[0 for i in range(g*2)] for j in range(len(XY[0]))]
Y = [[0 for i in range(g*2)] for j in range(len(XY[1]))]



if len(XY[0]) > 0 :
    X[0][g+XY[0][0]] = 1
    if s[0] == "T" :
        X[0][g-XY[0][0]] = 1
        
    for i in range(1, len(XY[0])) :
        for j in range(g*2) :
            #print(X)
            if j - XY[0][i] >= 0 and X[i-1][j - XY[0][i]] == 1 :
                X[i][j] = 1
            if j + XY[0][i] <= g*2-1 and X[i-1][j + XY[0][i]] == 1 :
                X[i][j] = 1

if len(XY[1]) > 0 :

    Y[0][g+XY[1][0]] = 1
    Y[0][g-XY[1][0]] = 1
        
    for i in range(1, len(XY[1])) :
        for j in range(20000) :
            if j - XY[1][i] >= 0 and Y[i-1][j - XY[1][i]] == 1 :
                Y[i][j] = 1
            if j + XY[1][i] <= g*2-1 and Y[i-1][j + XY[1][i]] == 1 :
                Y[i][j] = 1

if X == [] :
    X = [[0 for i in range(g*2)]]
if Y == [] :
    Y = [[0 for i in range(g*2)]]

if ((len(XY[0]) == 0 and x == 0) or X[-1][g+x] == 1) and ((len(XY[1]) == 0 and y == 0) or Y[-1][g+y] == 1) :
    print("Yes")
else :
    print("No")


### FIXED CODE ###

s = input()
x, y = map(int, input().split())
n = len(s)

D = [[], []]
st_x = 0
st_y = 0
st = 0
while st <= len(s)-1 and s[st] == "F":
    x -= 1
    st += 1

di = 0
for i in range(st, n):
    if s[i] == "T":
        di = (di+1) % 2
        D[di].append(0)
    else:
        D[di][-1] += 1

# print(D)


ANS = [0, 0]
st_po = [0, 0]
go_po = [x, y]
for i in range(2):
    mid = sum(D[i]) + 5
    DP = [[0] * (mid*2) for i in range(len(D[i]) + 1)]
    DP[0][st_po[i] + mid] = 1
    for j in range(len(D[i])):
        dd = D[i][j]
        for k in range(len(DP[0])):
            aa = 0
            bb = 0
            if 0 <= k-dd <= len(DP[0])-1:
                aa = DP[j][k-dd]
            if 0 <= k+dd <= len(DP[0])-1:
                bb = DP[j][k+dd]

            DP[j+1][k] = int(aa or bb)

    if 0 <= go_po[i]+mid <= len(DP[0])-1:
        ANS[i] = DP[-1][go_po[i]+mid]
    # print("len",mid*2)
    #if i == 1:
        # print(DP[1][7999+mid])
# print(ANS)

print("Yes" if ANS[0] and ANS[1] else "No")
### BUGGY CODE ###

K = int(input())
a = 0
out = '-1'
for n in range(K):
  a += 7 * (10 ** n)
  if a % K == 0:
    out = n + 1
    break
print(out)


### FIXED CODE ###

K = int(input())
ans = '-1'
mod = 7%K
path = [mod]
for i in range(1,K+1):
  if mod == 0:
    ans = i
    break
  mod = (mod*10 + 7)%K
  path.append(mod)
  if mod == path[0]:
    ans = '-1'
    break
print(ans)
### BUGGY CODE ###

import math
import numpy as np

n, m = map(int, input().split())
prices = np.array(list(map(int, input().split())))

for _ in range(m):
    max_index = np.argmax(prices)
    prices[max_index] = prices[max_index] / 2

total = 0
for price in prices:
    total += math.floor(price)

print(total)


### FIXED CODE ###

import math
import heapq

n, m = map(int, input().split())
prices = list(map(int, input().split()))
hq = []


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


# 優先度付キューの作成
for price in prices:
    _heappush_max(hq, price)

# 割引適用
for _ in range(m):
    target = _heappop_max(hq)
    _heappush_max(hq, target/2)

total = 0
for price in hq:
    total += math.floor(price)

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

n=int(input())
a=[int(input()) for i in range(n)]
A,B=sorted(a,reverse=True)[0:2]
for i in range(n):
    if i==a.index(max(a)):
        print(B)
    else:
        print(A)

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
A,B=sorted(a,reverse=True)[0:2]
for i in range(n):
    if a[i]==A:
        print(B)
    else:
        print(A)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
hN = LIST()

# dp[足場番号] = そこまで行くための最小コスト
dp = [INF] * (N)
dp[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            # j個先に跳ぶ
            dp[i+j] = min(dp[i] + abs(hN[i+j]-hN[i]), dp[i+j])
print(dp[N-1])


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
hN = LIST()

# dp[足場番号] = そこまで行くための最小コスト
dp = [INF] * (N)
dp[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            # j個先に跳ぶ
            dp[i+j] = min(dp[i] + abs(hN[i+j]-hN[i]), dp[i+j])
print(dp[N-1])
### BUGGY CODE ###

import numpy as np
n = int(input())
H = np.array([list(map(int, input().split())) for _ in range(n)], dtype = np.int)
dp = np.zeros((n, 3), dtype = np.int)
dp[0] = H[0]
def except_ind(num):
    ind = np.ones((3, ), dtype = bool)
    ind[num] = False
    return ind
for i in range(1, n):
    for j in range(3):
        dp[i][j] = np.max(dp[i - 1][except_ind(j)]) + H[i][j]
print(np.max(dp[n - 1]))


### FIXED CODE ###

n = int(input())
H = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * 3 for _ in range(n)]
dp[0] = H[0]
for i in range(1, n):
    dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + H[i][0]
    dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + H[i][1]
    dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + H[i][2]
print(max(dp[n - 1]))
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
T=min(A[min(K,len(A)-1)],B[min(K,len(B))-1],C[min(K,len(C)-1)])

L=[]
for i in range(min(K,len(A))):
    if A[i]<T:continue
    for j in range(min(K,len(B))):
        if B[i]<T:continue
        for k in range(min(K,len(C))):
            if C[i]<T:continue
            L.append(A[i]+B[j]+C[k])
L.sort(reverse=True)
for p in range(K):
    print(L[p])

### FIXED CODE ###

import heapq
def hq(x,y,z):
    return (-A[x-1]-B[y-1]-C[z-1],x,y,z)
X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

visited=[hq(1,1,1)]
q=[]
heapq.heappush(q,hq(1,1,1))
for _ in range(K):
    e,x,y,z=heapq.heappop(q)
    if x+1<=X and hq(x+1,y,z) not in visited:
        heapq.heappush(q,hq(x+1,y,z))
        visited.append(hq(x+1,y,z))
    if y+1<=Y and hq(x,y+1,z) not in visited:
        heapq.heappush(q,hq(x,y+1,z))
        visited.append(hq(x, y+1, z))
    if z+1<=Z and hq(x,y,z+1) not in visited:
        heapq.heappush(q,hq(x,y,z+1))
        visited.append(hq(x, y, z+1))
visited.sort()
for i in visited[0:K]:
    print(-i[0])
### BUGGY CODE ###

import pprint
import copy
N=int(input())
S=input()
dig=[[] for i in range(10)]
chkigid=[0]*10
ansdigid=[0]*10
#print(dig)
cnt=0
for i in range(N):
    dig[int(S[i])].append([int(S[i]),chkigid[int(S[i])],i])#dig[int(S[i])][chkigid[int(S[i])]][2]=i
    chkigid[int(S[i])]=chkigid[int(S[i])]+1
    #pprint.pprint(dig)
    #pprint.pprint(chkigid)
    #input()
for i in range(10):
    for j in range(10):
        dig2=copy.deepcopy(dig)
        v1 = float("inf")
        if len(dig2[i])!=0:
            v1 = dig2[i][0][2]
            dig2[i].pop(0)#pop(dig2[i][0])
        v2 = float("inf")
        for k in range(len(dig2[j])):
            #print(dig2[j][len(dig2[j])-1- k])
            if len(dig2[j])!=0:
                v2=dig2[j][len(dig2[j])-1-k][2]
                dig2[j].pop(len(dig2[j])-1-k)
                break
        if (v1<v2)and(v1!=float("inf"))and(v2!=float("inf")):
            for k in range(10):
                for l in range(len(dig2[k])):
                    if v1<dig2[k][l][2]<v2:
                        #print(dig2[k][l][0])
                        cnt=cnt+1
                        break
        #pprint.pprint(dig2)
        #print(i,v1,j,v2,cnt)
        #input()
print(cnt)




### FIXED CODE ###

import pprint
import copy
N=int(input())
S=input()
dig=[[] for i in range(10)]
chkigid=[0]*10
ansdigid=[0]*10
#print(dig)
cnt=0
for i in range(N):
    dig[int(S[i])].append(i)#dig[int(S[i])][chkigid[int(S[i])]][2]=i
    chkigid[int(S[i])]=chkigid[int(S[i])]+1
    #pprint.pprint(dig)
    #pprint.pprint(chkigid)
    #input()
#print(dig)
for i in range(10):
    for j in range(10):
        #dig2=copy.deepcopy(dig)
        v1 = float("inf")
        if len(dig[i])!=0:
            v1 = dig[i][0]
        v2 = float("inf")
        if len(dig[j])!=0:
            v2= dig[j][len(dig[j])-1]
        if (v1<v2)and(v1!=float("inf"))and(v2!=float("inf")):
            for k in range(10):
                for l in range(len(dig[k])):
                    if v1<dig[k][l]<v2:
                        #print(dig2[k][l][0])
                        cnt=cnt+1
                        break
        #pprint.pprint(dig)
        #print(i,v1,j,v2,cnt)
        #input()
print(cnt)
### BUGGY CODE ###

n , m = map(int,input().split())
a = [1] * n
ans = 0

for i in range(m):
    l , r = map(int,input().split())
    for j in range(n):
        if l > j + 1 or j + 1 > r:
            a[j] = 0
            
for i in range(n):
    ans += a[i]
    
print(ans)        

### FIXED CODE ###

n , m = map(int,input().split())
a , b = 1 , 100000

for i in range(m):
    l , r = map(int,input().split())
    if a <= l:
        a = l
    if b >= r:
        b = r
        
c = b - a + 1
if c > 0:
    print(c)
else:
    print(0)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def calc_comb(zeros, ones, length):
    return (2**ones * 3**(length - ones - zeros)) % MOD

def main():
    # L = int('0b'+SI(), 0)
    L = SI()

    count_one = 0
    count_zero = 0
    comb = 0
    for char in L:
        if char == '0':
            count_zero += 1
        elif char == '1':
            count_one += 1
            comb += calc_comb(count_zero + 1, count_one -1, len(L))
            comb %= MOD

    comb += calc_comb(count_zero, count_one, len(L))  # Lの最後が0だったとしても1だったとしても、a+b = L の場合が計算されていない。
    comb %= MOD

    print(comb)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def calc_comb(zeros, ones, length):
    return (pow(2,ones,MOD) * pow(3,(length - ones - zeros),MOD)) % MOD

def main():
    # L = int('0b'+SI(), 0)
    L = SI()

    count_one = 0
    count_zero = 0
    comb = 0
    for char in L:
        if char == '0':
            count_zero += 1
        elif char == '1':
            count_one += 1
            comb += calc_comb(count_zero + 1, count_one -1, len(L))
            comb %= MOD

    comb += calc_comb(count_zero, count_one, len(L))  # Lの最後が0だったとしても1だったとしても、a+b = L の場合が計算されていない。
    comb %= MOD

    print(comb)

main()
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    k,q = LI()
    d = LI()
    aa = [LI() for _ in range(q)]

    def f(n,x,m):
        e = [c%m for c in d]
        n -= 1
        s = sum(e)
        t = s * (n//k) + sum(e[:n%k])
        xt = x + t
        z = [1 if c == 0 else 0 for c in e]
        zs = sum(z) * (n//k) + sum(z[:n%k])
        # print(xt, x, m, zs,n%k)
        return n - (xt//m - x//m) - zs

    r = [f(n,x,m) for n,x,m in aa]
    return JA(r, "\n")


print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    k,q = LI()
    d = LI()
    aa = [LI() for _ in range(q)]

    def f(n,x,m):
        e = [c%m for c in d]
        n -= 1
        s = sum(e)
        t = s * (n//k) + sum(e[:n%k])
        xt = x + t
        z = [1 if c == 0 else 0 for c in e]
        zs = sum(z) * (n//k) + sum(z[:n%k])
        # print(xt, x, m, zs,n%k)
        return n - (xt//m - x//m) - zs

    r = [f(n,x,m) for n,x,m in aa]
    return JA(r, "\n")


print(main())
### BUGGY CODE ###

A = input()
ans = set()
for i in range(len(A)):
    for j in range(i+1, len(A)+1):
        S = A[:i]+A[i:j][::-1]+A[j:]
        if S not in ans:
            ans.add(S)
print(len(ans))


### FIXED CODE ###

import collections

A = input()
c = collections.Counter(A)

ans = len(A)*(len(A)-1)//2+1

for v in c.values():
    if v >= 2:
        ans -= v*(v-1)//2

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

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

ans = 10 ** 20

for i in range(1, N):
    ans = min(ans, abs(sum(a[:i]) - sum(a[i:])))

print(ans)


### FIXED CODE ###

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

ans = 10 ** 20

s1 = a[0]
s2 = sum(a[1:])
ans = abs(s1 - s2)
if len(a)==2:
    print(ans)
else:
    for i in range(1, N-1):
        s1 = s1 + a[i]
        s2 = s2 - a[i]
        ans = min(ans, abs(s1 - s2))

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

import pprint
def main():
    H, W = (int(_) for _ in input().split())
    S = [input() for _ in range(H)]
    yoko = [[0] * W for _ in range(H)]
    tate = [[0] * W for _ in range(H)]

    for i in range(H):
        right = 0
        cc = 0
        for left in range(W):
            if S[i][left] == '#':
                cc = 0
                right += 1
                continue
            while right < W and S[i][right] == '.':
                right += 1
            cc = right - left
            if left > 0 and S[i][left-1] == '.': yoko[i][left] = yoko[i][left-1]
            else: yoko[i][left] = cc
    for i in range(W):
        bottom = 0
        cc = 0
        for top in range(H):
            if S[top][i] == '#':
                cc = 0
                bottom += 1
                continue
            while bottom < H and S[bottom][i] == '.':
                bottom += 1
            cc = bottom - top
            if top > 0 and S[top-1][i] == '.': tate[top][i] = tate[top-1][i]
            else: tate[top][i] = cc
    output = 0
    for i in range(H):
        for j in range(W):
            output = max(output, yoko[i][j]+tate[i][j]-1)
    print(output)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    H, W = (int(_) for _ in input().split())
    S = [input() for _ in range(H)]
    yoko = [[0] * W for _ in range(H)]
    tate = [[0] * W for _ in range(H)]

    for i in range(H):
        right = 0
        cc = 0
        for left in range(W):
            if S[i][left] == '#':
                cc = 0
                right += 1
                continue
            while right < W and S[i][right] == '.':
                right += 1
            cc = right - left
            if left > 0 and S[i][left-1] == '.': yoko[i][left] = yoko[i][left-1]
            else: yoko[i][left] = cc
    for i in range(W):
        bottom = 0
        cc = 0
        for top in range(H):
            if S[top][i] == '#':
                cc = 0
                bottom += 1
                continue
            while bottom < H and S[bottom][i] == '.':
                bottom += 1
            cc = bottom - top
            if top > 0 and S[top-1][i] == '.': tate[top][i] = tate[top-1][i]
            else: tate[top][i] = cc
    output = 0
    for i in range(H):
        for j in range(W):
            output = max(output, yoko[i][j]+tate[i][j]-1)
    print(output)
    return

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

N = int(input())
a = [int(input()) for _ in range(N)]
i = 0
ans = 0
while (1):
    i = a[i] - 1
    ans += 1
    if i == 0:
        print(-1)
        break
    elif i == 1:
        print(ans)
        break


### FIXED CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
i = 1
ans = 0
for j in range(N):
    i = a[i - 1]
    ans += 1
    if i == 2:
        print(ans)
        exit()
print(-1)
### BUGGY CODE ###

import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    S = input()
    r,g,b = "R","G","B"

    def get_other(x,y):
        if x in [r,g] and y in [r,g]:
            return b
        if x in [r,b] and y in [r,b]:
            return g
        if x in [g,b] and y in [g,b]:
            return r

    rs = [0] * (N+1)
    gs = [0] * (N+1)
    bs = [0] * (N+1)

    for i in range(N):
        rs[i+1] = ((S[i] == r) + 0) + rs[i]
        gs[i+1] = ((S[i] == g) + 0) + gs[i]
        bs[i+1] = ((S[i] == b) + 0) + bs[i]

    s_dic = {r:rs,b:bs,g:gs}

    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            if S[i] != S[j]:
                not_k = 2 * j - i
                other = get_other(S[i],S[j])

                counter = s_dic[other]

                ans += counter[N] - counter[j+1]
                if not_k < len(S) and S[not_k] == other:
                    ans -= 1

    print(ans)



if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    S = input()
    r,g,b = "R","G","B"

    def get_other(x,y):
        if x in [r,g] and y in [r,g]:
            return b
        if x in [r,b] and y in [r,b]:
            return g
        if x in [g,b] and y in [g,b]:
            return r

    rs = [0] * (N+1)
    gs = [0] * (N+1)
    bs = [0] * (N+1)

    for i in range(N):
        rs[i+1] = ((S[i] == r) + 0) + rs[i]
        gs[i+1] = ((S[i] == g) + 0) + gs[i]
        bs[i+1] = ((S[i] == b) + 0) + bs[i]

    s_dic = {r:rs,b:bs,g:gs}

    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            if S[i] != S[j]:
                not_k = 2 * j - i
                other = get_other(S[i],S[j])

                counter = s_dic[other]

                ans += counter[N] - counter[j+1]
                if not_k < len(S) and S[not_k] == other:
                    ans -= 1

    print(ans)



if __name__ == "__main__":
  main()