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

N = int(input())
a = [int(input()) for _ in range(N) ]
hist = [1]
bottun = 0
i = 0

while True:
    # print(hist)
    bottun = a[hist[i]-1]
    # print(bottun)
    for j in hist:
        if bottun == j:
            print(-1)
            # print("hoge")
            exit()
    
    if bottun == 2:
        print(len(hist))
        exit()
    
    hist.append(bottun)
    i += 1


### FIXED CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
hist = [0] * N
bottun = a[0]
cnt = 1
hist[0] = 1

while True:
    # print(hist)
    # print(bottun)
    if hist[bottun-1] == 1:
        print(-1)
        exit()
    
    if bottun == 2:
        print(cnt)
        exit()
    
    hist[bottun-1] = 1
    bottun = a[bottun-1]
    cnt += 1
### BUGGY CODE ###

N = int(input())
numbers_full = [int(input()) for _ in range(N)]

numbers_minus1 = numbers_full
for i, tmp in enumerate(numbers_full):
  numbers_minus1[i] = 0
  print(str(max(numbers_minus1)))
  numbers_minus1[i] = tmp

### FIXED CODE ###

N = int(input())
number_list = [int(input()) for _ in range(N)]

sorted_num = sorted(number_list)
number_max = sorted_num[-1]
number_second_max = sorted_num[-2]

if number_max == number_second_max:
  output_always_max = True
else:
  output_always_max = False

for number in number_list:
  if output_always_max:
    print(str(number_max))
  else:
    if number == number_max:
      print(str(number_second_max))
    else:
      print(str(number_max))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt=0
for i in range(N-1):
    for j in range(i+1, N):
        cnt += A[i]*A[j]
print(cnt%((10**9)+7))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = sum(A)
cnt = 0
for i in range(N-1):
    B -= A[i]
    cnt += A[i]*B

print(cnt%((10**9)+7))
### BUGGY CODE ###

n = int(input())
s = input()

w = [0]
e = [0]

for i in range(1, n):

    if (s[i-1] == 'W'):
        w.append(w[-1] + 1)
    else:
        w.append(w[-1])


for j in range(n-2, -1, -1):

    if (s[j+1] == 'E'):
        e.insert(0, e[0] + 1)
    else:
        e.insert(0, e[0])


result = []

for i in range(n):
    result.append(e[i] + w[i])

print(min(result))

### FIXED CODE ###

n = int(input())
s = input()

w = [0]
e = [0]

tmp_w = 0
tmp_e = 0

for i in range(1, n):

    j = (n - 1) - i

    if (s[i-1] == 'W'):
        w.append(tmp_w + 1)
        tmp_w += 1
    else:
        w.append(tmp_w)

    if (s[j+1] == 'E'):
        e.append(tmp_e + 1)
        tmp_e += 1
    else:
        e.append(tmp_e)

e.reverse()

ans = 10 ** 6 
for i in range(n):
    ans = w[i] + e[i] if w[i] + e[i] < ans else ans

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

from collections import*
n,k,*h=map(int,open(0).read().split())
dp=defaultdict(int)

for i in range(1,n+1):
    dp[i]=float("inf")
dp[0]=0
for i in range(n):
    for j in range(1,k+1):
        if i+j<n:
            dp[i+j]=min(abs(h[i]-h[i+j])+dp[i],dp[i+j])
            #print(dp)
print(dp[n-1])

### FIXED CODE ###

from collections import*
n,k,*h=map(int,open(0).read().split())
dp=defaultdict(int)

for i in range(1,n+1):
    dp[i]=float("inf")
dp[0]=0
for i in range(n):
    for j in range(1,k+1):
        if i+j<n:
            dp[i+j]=min(abs(h[i]-h[i+j])+dp[i],dp[i+j])
        else:
            break
print(dp[n-1])
### BUGGY CODE ###

n = int(input())
for i in range(1,n + 1):
    p = 0
    k = i
    for x in range(1,k - 1):
        for y in range(1,k - x):
            for z in range(1,k - x - y):
                if (x ** 2) + (y ** 2) + (z ** 2) + (x * y) + (y * z) + (x * z) == k:
                    p += 1
    print(p)

### FIXED CODE ###

import math
n = int(input())
t = [0] * (n + 1)
m = math.floor(math.sqrt(n))

for i in range(1,m):
    for j in range(1,m):
        for k in range(1,m):
            p = i*i+j*j+k*k+i*j+j*k+i*k
            if p <= n:
                t[p] += 1

for i in range(1,n + 1):
    print(t[i])
### BUGGY CODE ###

import bisect
n,m = map(int,input().split())
ab = [[0] for _ in range(m)]

day_max = [0 for _ in range(m)]
for i in range(n):
    a,b = map(int,input().split())
    if a<= m:
        bisect.insort(ab[a-1],b)

for i in range(m):
    day_max[i] = ab[i][-1]
    if day_max[i] > 0:
        ab[i] = ab[i][0:-1]

# print(ab)
# print(day_max)

ans = 0
for day in range(m):
    gain = 0
    dayi = -1
    for i in range(day+1):
        if gain < day_max[i]:
            gain = day_max[i]
            dayi = i
    if dayi != -1:
        ans += day_max[dayi]
        day_max[dayi] = ab[dayi][-1]
        if day_max[dayi] > 0:
            ab[dayi] = ab[dayi][0:-1]
    # print(ans, day, dayi)

print(ans)


### FIXED CODE ###

import heapq
import bisect

n,m = map(int,input().split())
ab = [[0,0,0] for _ in range(n)]

for i in range(n):
    a,b = map(int,input().split())
    ab[i] = [-b,a,b]

ab = sorted(ab, key=lambda x:x[1])

# print(ab)

day = 1
# ans = []
ans = 0
pqueue = []

for i in range(n):
    if ab[i][1] > m:
        break

    if ab[i][1] <= day:
        heapq.heappush(pqueue, ab[i])
    else:
        for j in range(day, ab[i][1]):
            if len(pqueue) > 0:
                ans += heapq.heappop(pqueue)[2]
                # ans += [heapq.heappop(pqueue)[2]] // debug
                day = ab[i][1]
        heapq.heappush(pqueue, ab[i])
    # print(f"i:{i} day:{day} ans:{ans} queue:{pqueue}")

for k in range(day, m+1):
    if len(pqueue) > 0:
        ans += heapq.heappop(pqueue)[2]
        # ans += [heapq.heappop(pqueue)[2]] //debug
        # print(f"## i:{i} day:{k} ans:{ans} queue:{pqueue}")

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

from itertools import accumulate


def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    for ope_count in range(operations):
        temp = [0] * (number + 1)
        for i, v in enumerate(dists):
            left = max(i - v, 0)
            right = min(i + v + 1, number)
            temp[left] += 1
            temp[right] -= 1
        templi = list(accumulate(temp))
        if templi == dists:
            dists = templi
            break
        else:
            dists = templi

    print(*list(dists)[:-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

from itertools import accumulate


def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    for ope_count in range(operations):
        temp = [0] * (number + 1)
        for i, v in enumerate(dists):
            left = max(i - v, 0)
            right = min(i + v + 1, number)
            temp[left] += 1
            temp[right] -= 1
        templi = list(accumulate(temp))
        if templi == dists:
            break
        else:
            dists = templi

    print(*list(dists)[:-1])


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

S = input()
i = 0
j = 4
count = 0
if len(S) < 4:
    print(0)
    exit()
while True:
    if int(S[i:j]) % 2019 == 0:
        count += 1
    j += 1
    if j == len(S) + 1:
        if i == len(S) - 3:
            break
        else:
            j = i + 4
            i += 1

print(count)

### FIXED CODE ###

S = input()
mod_list = [0 for i in range(2019)]
mod_list[0] += 1
number = 0
ten_count = 1
for s in S[::-1]:
    number += pow(10, ten_count, 2019) * int(s)
    ten_count += 1
    mod_list[number % 2019] += 1

ans = 0
for i in mod_list:
    if i > 1:
        ans += i * (i - 1) // 2

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

N, M = list(map(int, input().split(' ')))

for _ in range(M):
    l, r = list(map(int, input().split(' ')))
    
    if _ == 0:
        if r > N:
            r = N
        ans = set(range(l, r+1))
        
    else:
        if r > N:
            r = N
        _ans = ans
        ans = set(range(l, r+1))
        ans = ans & _ans

print(len(ans))

### FIXED CODE ###

N, M = list(map(int, input().split(' ')))

L = 1
R = N

for _ in range(M):
    l, r = list(map(int, input().split(' ')))
    if l > L:
        L = l
    if r < R:
        R = r

ans = R-L+1
if ans >= 0:
  print(ans)
else:
  print(0)
### BUGGY CODE ###

import bisect
import sys
import math
input = sys.stdin.readline
import functools

from collections import defaultdict

############ ---- Input Functions ---- ############

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

############ ---- Solution ---- ############

def diff(S, i, T):
    res = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            res += 1
    return res

def solve():
    [N, M] = inlt()
    uf = [i for i in range(N)]

    def root(i):
        j = i
        while uf[j] != j:
            j = uf[j]
        uf[i] = j
        return j

    def union(i, j):
        uf[root(i)] = root(j)

    for i in range(M):
        [a, b] = inlt()
        union(a - 1, b - 1)

    groups = defaultdict(int)
    res = 0
    for i in range(N):
        r = root(i)
        groups[r] += 1
        res = max(res, groups[r])
    
    return res

    

if len(sys.argv) > 1 and sys.argv[1].startswith("input"):
    f = open("./" + sys.argv[1], 'r')
    input = f.readline

res = solve()
print(str(res))


### FIXED CODE ###

import bisect
import sys
import math
input = sys.stdin.readline
import functools

from collections import defaultdict

############ ---- Input Functions ---- ############

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

############ ---- Solution ---- ############

def dfs(i, edges, visited):
    s = []
    if not visited[i]:
        s.append(i)
        visited[i] = True
    res = 0
    while len(s) > 0:
        v = s.pop()
        res += 1
        for i in edges[v]:
            if not visited[i]:
                s.append(i)
                visited[i] = True

    return res

def solve():
    [N, M] = inlt()
    edges = defaultdict(set)
    visited = [False for i in range(N)]

    for i in range(M):
        [a, b] = inlt()
        edges[a - 1].add(b - 1)
        edges[b - 1].add(a - 1)

    res = 0
    for i in range(N):
        res = max(res, dfs(i, edges, visited))
    
    return res

    

if len(sys.argv) > 1 and sys.argv[1].startswith("input"):
    f = open("./" + sys.argv[1], 'r')
    input = f.readline

res = solve()
print(str(res))
### BUGGY CODE ###

n = int(input())
s = input()

compressed = s[0]
for i in range(1, n):
    if s[i] != s[i - 1]:
        compressed += s[i]

print(len(compressed))

### FIXED CODE ###

n = int(input())
s = input()

compressed = s[0]
for i in range(1, n):
    if s[i] != s[i - 1]:
        compressed += s[i]

print(len(compressed))
### BUGGY CODE ###

N = int(input())
D = [list(map(int, input().split())) for _ in range(N)]
D.sort(reverse=True)

A=0
B=0
while D!=[]:
  A+=D[0][0]
  D.pop(0)
  if D==[]:
    break
  tmp=max(D, key=lambda x:x[1])
  B+=tmp[1]
  D.remove(tmp)
  
print(A-B)

### FIXED CODE ###

N = int(input())
D=[]
b=0
for _ in range(N):
  A,B=map(int, input().split())
  D.append([A,B,A+B])
  b+=B
D.sort(reverse=True, key=lambda x:x[2])

ans=0
while D!=[]:
  ans+=D[0][2]
  D.pop(0)
  if D!=[]:
    D.pop(0)
  
print(ans-b)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lst = []
ans = []
for i in range(n-1):
    if s[i:i+2] == 'AC':
        lst.append(i+1)

for i in range(q):
    cnt = 0
    l,r = map(int,input().split())
    for j in range(len(lst)):
        if l<=lst[j]<r:
            cnt += 1
    ans.append(cnt)

for i in range(q):
    print(ans[i])

### FIXED CODE ###

from itertools import accumulate
n,q = list(map(int,input().split()))
s = input()
A = [list(map(int,input().split())) for i in range(q)]

flg = []
for i in range(n-1):
    tmp_s = s[i:i+2]
    if tmp_s == 'AC':
        flg.append(1)
    else:
        flg.append(0)

flg2 = [0] + flg
flg2 = list(accumulate(flg2))


for a in A:
    print(flg2[a[1]-1] - flg2[a[0]-1])
### BUGGY CODE ###

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

lst1 = [int(input()) for i in range(M)]

def fib(n):
  a, b = 1, 2
  for i in range(1,n+1):  
    if (i == 1):
      if (i in lst1):
        a, b = 0, 1
      yield a
    else:
      if (i in lst1):
        a, b = 0, a
      else:
        a, b = b, b+a
      yield a

lst2 = [i for i in fib(N)]
print(lst2[-1] % 1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
D=[1] * (n + 1)
for _ in range(m):
    D[int(input())] = 0
for i in range(n+1):
    if i > 1:
        D[i] = (D[i-1] + D[i-2]) % 1000000007 * D[i]
print(D[i])
### BUGGY CODE ###

n,m = map(int, input().split())
a = [int(input()) for _ in range(m)]

nums = [0]*(n+1)
nums[0] = 1
if 1 not in a: nums[1] = 1

for i in range(2,n+1):
  if i not in a: nums[i] = nums[i-1] + nums[i-2]
  else: nums[i] = 0
print(nums[n]%(10**9+7))

### FIXED CODE ###

n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
inf = 1000000007

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1
else:
  dp[1] = 0
  
for i in range(2, n+1):
  if i in a:
    continue
  dp[i] = dp[i - 1] + dp[i - 2]
  dp[i] %= inf
  
print(dp[n])
### BUGGY CODE ###

N = int(input())
TA = [list(map(int, input().split())) for _ in range(N)]

T, A = 0, 0
for t, a in TA:
    if T == 0 and A == 0:
        T = t
        A = a
        continue
    if t == a:
        M = max(T, A)
        T = M
        A = M
    elif t < a:
        n = (T // t) * t
        while n < T or a * (n // t) < A:
            n += t
        T = n
        A = a * (T // t)
    else:
        n = (A // a) * a
        while n < A or t * (n // a) < T:
            n += a
        A = n
        T = t * (A // a)
print(A + T)

### FIXED CODE ###

N = int(input())
TA = [list(map(int, input().split())) for _ in range(N)]

T, A = 0, 0
for t, a in TA:
    if T == 0 and A == 0:
        T = t
        A = a
        continue
    if t == a:
        M = max(T, A)
        T = M
        A = M
    elif t < a:
        n = max((T // t) * t, (A // a) * t)
        while n < T or a * (n // t) < A:
            n += t
        T = n
        A = a * (T // t)
    else:
        n = max((A // a) * a, (T // t) * a)
        while n < A or t * (n // a) < T:
            n += a
        A = n
        T = t * (A // a)
print(A + T)
### BUGGY CODE ###

def insert(a, data):
    a.append(data)
    heapinc(a, len(a)-1)

def heapinc(a, index):
    parent = (index - 1) // 2
    if parent >= 0:
        if a[parent] < a[index]:
            memo = a[parent]
            a[parent] = a[index]
            a[index] = memo
            heapinc(a, parent)

def extract(a):
    root = a[0]
    a[0] = a[-1]
    del a[-1]
    maxheapify(a, 0)
    return root

def maxheapify(a, i):
    l = i*2 + 1
    r = i*2 + 2

    if r < len(a):
        if a[l] > a[i]:
            largest = l
        else:
            largest = i
        if a[r] > a[largest]:
            largest = r

        if largest != i:
            memo = a[i]
            a[i] = a[largest]
            a[largest] = memo
            maxheapify(a, largest)

    elif l < len(a):
        if a[l] > a[i]:
            largest = l
        else:
            largest = i
        if largest != i:
            memo = a[i]
            a[i] = a[largest]
            a[largest] = memo
            maxheapify(a, largest)

a = []
while 1:
    com = input().split()
    if com[0] == 'insert':
        insert(a, int(com[1]))
    elif com[0] == 'extract':
        print(extract(a))
    else:
        break



### FIXED CODE ###

from heapq import *

a = []
while 1:
    com = input().split()
    if com[0] == 'end':
        break
    elif com[0] == 'insert':
        heappush(a, -int(com[1]))
    else:
        print(-heappop(a))
### BUGGY CODE ###

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

L_sorted = sorted(L)

count = 0
for i in range(0, N):
    for j in range(i+1,N):
        for k in range(j+1, N):
            if L_sorted[i] + L_sorted[j] > L_sorted[k]:
                count += 1
            else:
                break

print(count)

### FIXED CODE ###

from bisect import bisect_right

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

L_sorted = sorted(L)

count = 0
for i in range(N):  # longest stick
    for j in range(i):  # second longest stick
        r = bisect_right(L_sorted, L_sorted[i] - L_sorted[j])
        count += max(0, j - r)

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

N, Q = map(int, raw_input().split())
string = raw_input()
a = []
for i in range(Q):
    a.append(map(int, raw_input().split()))
for temp in a:
    print(string[temp[0]-1:temp[1]].count('AC'))

### FIXED CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
cnt = [0]
for i in range(N):
#    print(i)
#    print(string[i-2:i])
#    if i == 0:
#        cnt.append(0)
#        continue
    if string[i-1:i+1] == 'AC':
        cnt.append(cnt[i]+1)
        continue
    cnt.append(cnt[i])

for j in range(Q):
    #print(j)
    pare = map(int, raw_input().split())
    print(cnt[pare[1]] - cnt[pare[0]])
### BUGGY CODE ###

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]
nx=[]

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,k):
    i=1
    while True:
        if y+i>W-1 or C[x][y+i]!='.' or i>k:
            break
        else:
            nx.append([x,y+i])
            i+=1
    
    i=1
    while True:
        if y-i<0 or C[x][y-i]!='.' or i>k:
            break
        else:
            nx.append([x,y-i])
            i+=1
    
    i=1
    while True:
        if x+i>H-1 or C[x+i][y]!='.' or i>k:
            break
        else:
            nx.append([x+i,y])
            i+=1
    
    i=1
    while True:
        if x-i<0 or C[x-i][y]!='.' or i>k:
            break
        else:
            nx.append([x-i,y])
            i+=1

    return 0

C[x1-1][y1-1]=str(0)
keiro(x1-1,y1-1,K)
taisho=nx.copy()
result=1
for j in nx:
    C[j[0]][j[1]]=result

while C[x2-1][y2-1]=='.':
    nx=[]
    if len(taisho)==0 or result>10**6:
        result=-1
        break
    for l in taisho:
        keiro(l[0],l[1],K)
    result+=1
    for j in nx:
        C[j[0]][j[1]]=result
    taisho=nx.copy()

print(result)


### FIXED CODE ###

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]
nx=set([])

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,k):
    i=1
    while True:
        if y+i>W-1 or C[x][y+i]!='.' or i>k:
            break
        else:
            if (x,y+i) not in nx:
                nx.add((x,y+i))
            i+=1
    
    i=1
    while True:
        if y-i<0 or C[x][y-i]!='.' or i>k:
            break
        else:
            if (x,y-i) not in nx:
                nx.add((x,y-i))
            i+=1
    
    i=1
    while True:
        if x+i>H-1 or C[x+i][y]!='.' or i>k:
            break
        else:
            if (x+i,y) not in nx:
                nx.add((x+i,y))
            i+=1
    
    i=1
    while True:
        if x-i<0 or C[x-i][y]!='.' or i>k:
            break
        else:
            if (x-i,y) not in nx:
                nx.add((x-i,y))
            i+=1

    return 0

C[x1-1][y1-1]=0
keiro(x1-1,y1-1,K)
taisho=nx.copy()
result=1
for j in nx:
    C[j[0]][j[1]]=result

while C[x2-1][y2-1]=='.':
    nx=set([])
    if len(taisho)==0 or result>10**6:
        result=-1
        break
    for l in taisho:
        keiro(l[0],l[1],K)
    result+=1
    for j in nx:
        C[j[0]][j[1]]=result
    taisho=nx.copy()

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

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = [(0, x1, y1)]
    dist[x1][y1] = 0
    while q:
        d, i, j = heappop(q)
        if dist[i][j] < d: continue
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] <= d + 1: continue
                heappush(q, (d + 1, ni, nj))
                dist[ni][nj] = d + 1
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)
### BUGGY CODE ###

import math
N = int(input())
info = [list(map(int,input().split())) for i in range(N)]
def modify(l1,l2):
    k1 = math.ceil(l1[0]/l2[0])
    k2 = math.ceil(l1[1]/l2[1])
    bigin = min(k1,k2)
    end = max(k1,k2)
    for i in range(bigin,end+1):
        if l2[0] * i >= l1[0] and l2[1] * i >= l1[1]:
            l2[0] *= i
            l2[1] *= i
            break
for i in range(N-1):
    modify(info[i],info[i+1])
ans = sum(info[-1])
print(ans)

### FIXED CODE ###

N = int(input())
info = [list(map(int,input().split())) for i in range(N)]
def modify(l1,l2):
    # k >= b / a
    # a * k >= b
    k1 = l1[0]//l2[0]
    k2 = l1[1]//l2[1]
    k = max(k1,k2)
    for i in range(k,k+2):
        if l2[0] * i >= l1[0] and l2[1] * i >= l1[1]:
            l2[0] *= i
            l2[1] *= i
            break
for i in range(N-1):
    modify(info[i],info[i+1])
ans = sum(info[-1])
print(ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
count = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if L[i] < L[j] + L[k]:
                if L[j] < L[k] + L[i]:
                    if L[k] < L[i] + L[j]:
                        count += 1

print(count)


### FIXED CODE ###

from bisect import bisect_right
N = int(input())
L = list(map(int, input().split()))
count = 0
L.sort()
for i in range(N):
    for j in range(i):
        m = L[i] - L[j]
        k = bisect_right(L, m)
        n = max(0, j - k)
        count += n
print(count)
### BUGGY CODE ###

n = int(input())

print(sum(range(n)))

### FIXED CODE ###

n = int(input())

if n % 2 == 0:
  print(n * (n//2) - n//2)
else:
  print(n * (n //2))
### BUGGY CODE ###

N, K = map(int, input().split())
Nj = N
while True:
    Ni = Nj
    Nj = abs(Ni - K)
    if Ni > N:
        print(N)
        break
    elif Nj > Ni:
        print(Ni)
        break
    elif K == 1 or N == K:
        print(0)
        break
    else:
        continue


### FIXED CODE ###

n,k = map(int,input().split())
if n % k ==0:
    print(0)
else:
    l = [n]
    p = n//k
    c = n-(p*k)
    half = k//2
    while c > half:
        c = abs(c-k)
    l.append(c)
    print(min(l))
### BUGGY CODE ###

s=input()
n=len(s)

modlist=[]

for i in range(n):
  modlist.append(int(s[i:])%2019)

modlist.append(0)
 
result = 0
  
for i in range(2019):
  c = modlist.count(i)
  result += c*(c-1)/2

print(int(result))

### FIXED CODE ###

s = input()[::-1]

dp = [0]*2019
dp[0]=1
total = 0
a = 1

for i in list(s):
  total += int(i)*a
  total %= 2019
  dp[total] += 1
  a *= 10
  a %= 2019
count=0
  
for i in range(2019):
    count += dp[i]*(dp[i]-1)//2
 
print(count)