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

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        try :
            if ANS[a[1]+L-1] == None : 
                ANS[a[1]+L-1] = a[0]
                count += 1
        except IndexError : pass
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.997
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n, k = map(int,input().split())
lrl = []
for _ in range(k):
    lrl.append(list(map(int,input().split())))

N = 2 * n
# N: 処理する区間の長さ

data0 = [0]*(N+1)
data1 = [0]*(N+1)

mod = 998244353
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        x %= mod
        data[k] += x
        data[k] %= mod
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1)%mod)
    _add(data0, r, x*(r-1)%mod)
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        s %= mod
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

add(1, 2, 1)
for i in range(n):
    now = query(i+1, i+2) 
    for l, r in lrl:
        add(l+i+1, r+i+2, now % mod)

print(query(n, n+1) % mod)


### FIXED CODE ###

n, k = map(int,input().split())
lrl = []
for _ in range(k):
    lrl.append(list(map(int,input().split())))

N = 2 * n
# N: 処理する区間の長さ

data0 = [0]*(N+1)
data1 = [0]*(N+1)

mod = 998244353
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        x %= mod
        data[k] += x
        data[k] %= mod
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1)%mod)
    _add(data0, r, x*(r-1)%mod)
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        s %= mod
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

add(1, 2, 1)
for i in range(n):
    now = query(i+1, i+2) 
    for l, r in lrl:
        add(l+i+1, r+i+2, now % mod)

print(query(n, n+1) % mod)
### BUGGY CODE ###

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

ans = 0
for i in range(n):
  count = 1
  right = xl[i][0] + xl[i][1]
  for j in range(i+1,n):
    if right <= xl[j][0] - xl[j][1] :
      count += 1
      right = xl[j][0] + xl[j][1] 
  ans = max(ans,count)

print(ans)    

### FIXED CODE ###

n = int(input())

itv = []
for i in range(n):
  tx,tl = map(int,input().split())  
  itv.append([tx+tl,tx-tl] )

itv = sorted(itv)

ans = 0
right = float('-inf')

for i in range(n):  
  if right <= itv[i][1]:    
    ans += 1
    right = itv[i][0]
    
print(ans)
### BUGGY CODE ###

from heapq import heappush, heappop, merge

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = sorted(events)
constructions = []
i = 0
for _ in range(Q):
    d = int(input())
    while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
            heappush(constructions, events[i][2])
        else:
            temp = []
            while constructions[0] != events[i][2]:
                heappush(temp, heappop(constructions))
            heappop(constructions)
            constructions = list(merge(temp, constructions))
        i += 1
    print(constructions[0] if constructions else -1)

### FIXED CODE ###

from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

n, x, y = map(int, input().split())
kyori = []

def clc(i1, i2):
    return min(1 + abs(i2 - y) + abs(i1 - x), i2 - i1)

for k in range(1, n+1):
    for l in range(k+1, n+1):
        tmp = clc(k, l)
        kyori.append(tmp)

for i in range(n-1):
    cnt = 0
    for k in kyori:
        if k == i + 1:
            cnt += 1
    print(cnt)

### FIXED CODE ###

n, x, y = map(int, input().split())
kyori = []

def clc(i1, i2):
    if (i1 < x and i2 <= x) or (y <= i1 and y < i2):
        return i2 - i1
    else:
        return min(1 + abs(i2 - y) + abs(i1 - x), i2 - i1)

for k in range(1, n+1):
    for l in range(k+1, n+1):
        tmp = clc(k, l)
        kyori.append(tmp)
outs = [0 for _ in range(n-1)]
for k in kyori:
    outs[k-1] += 1
for i in range(n-1):
    print(outs[i])
### BUGGY CODE ###

n = int(input())
ans = 0
m = n // 2
if n%2==1:
  for i in range(1, m+1):
    ans += (i%(i+1)+(m+i)%(m+i+1))
else:
  for i in range(1, m+1):
    ans += (i%(i+1)+(m+i)%(m+i+1))
    if i == m:
      ans -= m*2
print(ans) 

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

L = input()
ans = 0
n = len(L)
def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        x %= 1000000007
        n //= 2

    return K * x
count = 0
for i in range(len(L)):
    if i == 0:
        ans += (pow(3,n-1) + 2) % 1000000007
        count += 1
    else:
        if L[i] == "1":
            ans += (pow(3,n-1)+1)%1000000007*(pow(2,count)%1000000007)
            count += 1
    n -= 1
print(ans%1000000007)


### FIXED CODE ###

L = input()
ans = 0
n = len(L)
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

count = 0
for i in range(len(L)):
    if i == 0:
        ans += (power_func(3,n-1,1000000007) + 2)
        ans %= 1000000007
        count += 1
    else:
        if L[i] == "1":
            ans += (power_func(3,n-1,1000000007)+1)*(power_func(2,count,1000000007))
            ans %= 1000000007
            count += 1
    n -= 1
print(ans%1000000007)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1, N + 1):
    n = N // i
    cnt = (n * (2 * i + (n - 1) * i)) // 2
    ans += cnt
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N + 1):
    n = N // i  # 項数n
    cnt = (n * (2 * i + (n - 1) * i)) // 2  # 初項i, 項数n の等差数列の和の公式
    ans += cnt
print(ans)
### BUGGY CODE ###

from collections import Counter
from itertools import product
 
N = int(input())
S = input().strip()
dic = Counter(S)
c = dic.most_common()
mod = 10**9 + 7
 
ans = 0
d = []
for x in c:
    if x[1] == 1:
        break
    else:
        d.append(x[1])
b = len(c)-len(d)
 
ls =list(product([0, 1], repeat=len(d)))
 
for x in ls:
    num = 1
    for z, y in zip(d, x):
        if y == 1:
            num = (z*num)%mod
    ans = (ans + num*(2**b))%mod
print(ans-1)

### FIXED CODE ###

from collections import Counter
from itertools import product
 
N = int(input())
S = input().strip()
dic = Counter(S)
mod = 10**9 + 7

ans = 1
for x in dic:
    ans = ans*(dic[x]+1)%mod
print(ans-1)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    MOD = 10**9+7
    
    dp = [[0 for _ in range((1<<N)+1)] for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        for s in range(1<<N):
            if dp[i][s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    dp[i+1][s|jb] += dp[i][s]
    
    print(dp[-1][(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    MOD = 10**9+7
    
    dp = [1] + [0 for _ in range(1<<N)]

    for i in range(N):
        use = [0 for _ in range((1<<N)+1)]
        for s in range(1<<N):
            if dp[s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    use[s^jb] += dp[s]
        dp = use
    
    print(dp[(1<<N)-1]%MOD)

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

# coding: utf-8
import fractions


def solve(arg: str) -> str:
    a, b = map(int, arg.split())
    div = [1]
    g = fractions.gcd(a, b)
    n = 2
    while n <= g:
        if a % n == 0 and b % n == 0:
            if(all([n % m != 0 for m in div if m != 1])):
                div.append(n)
                while g % n == 0:
                    g = int(g/n)
        n += 1

    return str(len(div))


if __name__ == "__main__":
    print(solve(input()))


### FIXED CODE ###

# coding: utf-8
import fractions


def solve(arg: str) -> str:
    a, b = map(int, arg.split())
    div = [1]

    g = fractions.gcd(a, b)
    n = 2
    while n*n <= g:
        if g % n == 0:
            div.append(n)
            while g % n == 0:
                g = int(g/n)
        n += 1
    if g != 1:
        div.append(g)

    return str(len(div))


if __name__ == "__main__":
    print(solve(input()))
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = []
a = 1
for i in range(K):
    a *= A[i]
B.append(a)
for i in range(N - K):
    a //= A[i]
    a *= A[K + i]
    B.append(a)
    ans = 'No'
    if a > B[i]:
        ans = 'Yes'
    print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N - K):
    ans = 'No'
    if A[i] < A[i + K]:
        ans = 'Yes'
    print(ans)
### BUGGY CODE ###

import math 
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime ", "not coprime"]

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
if gcd_list(A) != 1:
  print(ans[2])
  quit()
  
def seachPrimeNum(N):
    max = int(N ** (1 / 2))
    D = [0] * N
    D[0] = 1
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        nn = seachList[0]
        D[nn - 1] = nn
        primeNum.append(nn)
        tmp = nn
        for i in seachList:
          if i != nn:
            if i % tmp == 0:
              D[i - 1] = nn
        seachList = [i for i in seachList if i % tmp != 0]
    for i in seachList:
      D[i - 1] = i
    primeNum.extend(seachList)
    
    return primeNum, D  
  
primeNum, D = seachPrimeNum(1000000)
used = [0] * len(primeNum)

for i in range(N):
  now = A[i]
  q = []
  #print(now, D[now - 1])
  if (now == D[now - 1]) and (now != 1):
    q.append(now)
  else:
    while now != D[now - 1]:
      now = int(now / D[now - 1])
      if now in primeNum:
        q.append(now)
        
  for i in q:
    if used[primeNum.index(i)] == 0:
      used[primeNum.index(i)] = 1
    else:
      print(ans[1])
      quit()  

print(ans[0])


### FIXED CODE ###

from math import gcd
n = int(input())
a = [int(i) for i in input().split()]

g = a[0]
for i in range(n):
    g = gcd(g,a[i])
if g != 1:
    print("not coprime")
    exit()

m = max(a)
fac = [1]*(m+1)
for i in range(2,m+1):
    if fac[i] != 1:
      continue
    for j in range(i,m+1,i):
      fac[j] = i
      
s = set()
for i in range(n):
    x = fac[a[i]]
    if x == 1: 
      continue
    if x in s:
      print("setwise coprime")
      exit()
    s.add(x)
print("pairwise coprime")
### BUGGY CODE ###

#ALDS1_4-D Allocation

def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    while(w):
        tmp = w.pop(0)
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp

    c+=1
    if c>k:
        return False
    else:
        return True
    
n,k = input().split()
w=[]
for i in range(int(n)):
    t = int(input())
    w.append(t)

p = max(w)

while(1):
    x=w.copy()
    if(pIsAccptbl(x,int(k),p)):
        print(p)
        break
    else:
        p+=1

### FIXED CODE ###

from collections import deque

def isPa(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

def MaxInP(w,k,p):
    maxinp = 0
    tmp = 0
    d = deque(w)
    while(d):
        tmp += d.popleft();
        if(tmp > p):
            if(tmp > maxinp):
                maxinp = tmp
            tmp = 0
    return maxinp

n,k = [int(x) for x in input().split()]
w = deque()
for i in range(n):
    w.append(int(input()))
    
mean = int(sum(w)/k)
maxinp = MaxInP(w,k,mean)

if k == 1:
    print(mean)
else:
    minP = mean
    maxP = maxinp
    while(True):
        m = int ((minP + maxP)/2)
        if ( isPa(w,k,m) ):
            maxP = m
        else:
            minP = m
        if (minP+1 == maxP or minP == maxP):
            print(maxP)
            break
### BUGGY CODE ###

s=input()

a=0
ab=0
abc=0
q=0
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+3**q)%m
  elif s[i]=="B":
    ab=ab+a
  elif s[i]=="C":
    abc=(abc+ab)%m
  elif s[i]=="?":
    abc=(abc*3+ab)%m
    ab=ab*3+a
    a=(a*3+3**q)%m
    q+=1
print(abc)


### FIXED CODE ###

s=input()

a=0
ab=0
abc=0
q=1
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+q)%m
  elif s[i]=="B":
    ab=(ab+a)%m
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=(ab*3+a)%m
    a=(a*3+q)%m
    q=(q*3)%m
print(abc)
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()
    d = {'R': [], 'G': [], 'B': []}

    for i, c in enumerate(s):
        d[c].append(i)

    ans = 0

    perms = (('R', 'G', 'B'), ('R', 'B', 'G'), ('B', 'R', 'G'), ('B', 'G', 'R'), ('G', 'R', 'B'), ('G', 'B', 'R'))

    for p1, p2, p3 in perms:
        for i in d[p1]:
            for j in d[p2]:
                for k in d[p3]:
                    if j > i and k > j and k-j != j-i:
                        ans +=1

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
def main():
    n = int(input())
    s = input()
    d = Counter(s)
    ans = d['R'] * d['G'] * d['B']

    for i in range(n-2):
        for j in range(i+1, n-1):
            k = 2*j-i
            if s[i]!=s[j] and k < n and s[i] != s[k] and s[j] != s[k]:
                ans -= 1

    print(ans)

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

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]

C = [[0 for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

dp = [[[0 for k in range(6400)] for j in range(W)] for i in range(H)]
dp[0][0][C[0][0]] = 1

for i in range(H):
    for j in range(W):
        for k in range(6400):
            if not dp[i][j][k]:
                continue
            ni,nj = i+1,j+1
            if ni < H:
                if k+C[ni][j]<6400:
                    dp[ni][j][k+C[ni][j]] = 1
                dp[ni][j][abs(k-C[ni][j])] = 1
            if nj < W:
                if k+C[i][nj]<6400:
                    dp[i][nj][k+C[i][nj]] = 1
                dp[i][nj][abs(k-C[i][nj])] = 1

for k in range(6400):
    if dp[-1][-1][k]:
        print(k)
        break

### FIXED CODE ###

def main():

    H,W = map(int,input().split())
    A = [list(map(int,input().split())) for _ in range(H)]
    B = [list(map(int,input().split())) for _ in range(H)]

    C = [[0 for j in range(W)] for i in range(H)]

    for i in range(H):
        for j in range(W):
            C[i][j] = abs(A[i][j]-B[i][j])

    dp = [[0 for k in range(6400)] for g in range(H*W)]
    dp[0][C[0][0]] = 1

    for g in range(H*W):
        i,j = divmod(g,W)
        for k in range(6400):
            if not dp[i*W+j][k]:
                continue
            ni,nj = i+1,j+1
            if ni < H:
                if k+C[ni][j]<6400:
                    dp[ni*W+j][k+C[ni][j]] = 1
                dp[ni*W+j][abs(k-C[ni][j])] = 1
            if nj < W:
                if k+C[i][nj]<6400:
                    dp[i*W+nj][k+C[i][nj]] = 1
                dp[i*W+nj][abs(k-C[i][nj])] = 1

    for k in range(6400):
        if dp[-1][k]:
            print(k)
            break

main()
### BUGGY CODE ###

import collections
r, g, b, n = map(int, input().split())

#sum_rg = collections.Counter()  # TLE
sum_rg = collections.defaultdict(int)

for i in range(n + 1):
    if n < r*i:
        break
    for j in range(n + 1):
        if n < r*i + g*j:
            break
        sum_rg[r*i + g*j] += 1

ans = 0
for k in range(n + 1):
    if n < b*k:
        break
    ans += sum_rg[n - b*k]

#print(sum_rg)
print(ans)

### FIXED CODE ###

import collections
r, g, b, n = map(int, input().split())

#sum_rg = collections.Counter()
sum_rg = collections.defaultdict(int)

for i in range(n + 1):
    if n < r*i:
        break
    for j in range(n + 1):
        if n < r*i + g*j:
            break
        sum_rg[r*i + g*j] += 1

ans = 0
for k in range(n + 1):
    if n < b*k:
        break
    ans += sum_rg[n - b*k]

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

#!/usr/bin/env python3
import sys
import collections
import copy
def dellist(items, indexes):
    for index in sorted(indexes, reverse=True):
        del items[index]


def max_fetch(k,c,N):
    if c[0]*k <= N:
        return N//k
    else:
        return max_fetch(k-1,c[1:],N-c[0])



def solve(N: int, A: "List[int]"):
    counter = sorted(list(collections.Counter(A).values()),reverse=True)
    for i in range(1,N+1):
        if len(counter) < i:
            print(0)
            continue
        if counter[0]*i <= N:
            print(N//i)
            continue

        print(max_fetch(i,counter,N))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections

def solve(N: int, A: "List[int]"):
    counter = sorted(list(collections.Counter(A).values()),reverse=True)
    c_index = 0
    k=0
    for i in range(1,N+1):
        k+=1
        if len(counter)<i:
            print(0)
            continue
        while counter[c_index]*k > N and c_index<len(counter)-1:
            N-=counter[c_index]
            c_index+=1
            k-=1
        print(N//k)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

n = int(input())
a = [0]+[int(input()) for _ in [0]*n]
used = [False, True]+[False]*(n-1)
ans = 0
now = 1
while now!=2:
    b = a[now]
    if not used[b]:
        now = a[now]
        ans += 1
    else:
        print(-1)
        break
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = [0]+[int(input()) for _ in [0]*n]
ans = 0
now = 1
while now!=2:
    now = a[now]
    ans += 1
    if ans > n:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

from fractions import gcd
from itertools import accumulate
N=int(input())
A=[int(i) for i in input().split()]
GCD=[]
if len(A)==2:
    print(max(A))
else:
    for i in range(N):
        B=A.copy()
        B.remove(B[i])
        C=list(accumulate(B,gcd))
        GCD.append(C[-1])
    print(max(GCD))

### FIXED CODE ###

try:
    from fractions import gcd
except:
    from math import gcd
from itertools import accumulate
N=int(input())
A=[int(i) for i in input().split()]
l=[0]+list(accumulate(A,gcd))
g=list(reversed(list(accumulate(reversed(A),gcd))))+[0]

print(max([gcd(l[i-1],g[i]) for i in range(1,N+1)]))
### BUGGY CODE ###

def serch(s, index, li):
    h = []
    x = len(s) - 4
    for i in li:
        if s[i] + s[i+1] + s[i+2] == 'ABC':
            if 0 < i:
                if s[i-1] == 'A':
                    h.append(i-1)
            if i < x:
                h.append(i+2)
            s = s[0:i] + 'BCA' + s[i+3:]
            index += 1
    h = list(set(h))

    return s, index, h

S = input()

li = []

for i in range(len(S) - 2):
    if S[i] == 'A':
        li.append(i)

ans = 0

while len(li):
    S, ans, li = serch(S, ans, li)

print(ans)

### FIXED CODE ###

S = input()
S = S.replace('BC', 'X')

ans = 0
acc_A = 0
for s in S:
    if s=='A':
        acc_A += 1
    elif s=='X':
        ans += acc_A
    else:
        acc_A = 0

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

import sys
N=sys.stdin.readline().strip()
ans=0

length=len(N)

for r in range(1,length+1):
    for l in range(r):
        n=int(N[l:r])
        if n%2019==0:
            ans+=1
print ans 


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N=sys.stdin.readline().strip()
N=N[::-1]
#Lの先頭の0を入れるのは、何も数を選択しない状態はmod2019がゼロになるの意味
#19行目でx=0の際に、ans+=C[x]で1足されることになるので都合が良い
L=[0] 
val=0
for i,x in enumerate(N):
    val+=pow(10,i,2019)*int(x)
    L.append(val%2019)

C=defaultdict(lambda: 0)    #mod2019の出現個数を記録
ans=0
for x in L:
    ans+=C[x]   #自分とmod2019の結果が同じ値となる個数をansに足す
    C[x]+=1     #自分のmod2019の値を出現回数に+1カウント
print ans