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

N = int(input())
A = list(map(int, input().split()))
A_plus_i = [(i+1) + A[i] for i in range(N)]
A_minus_i = [(i+1) - A[i] for i in range(N)]
ans = 0
for i in range(N-1):
    ans += A_minus_i[i+1:].count(A_plus_i[i])
print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
i_plus_A = Counter([i + A[i] for i in range(N)])
i_minus_A = [i - A[i] for i in range(N)]
ans = 0
for x in i_minus_A:
    ans += i_plus_A[x]
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
l, r = [0]*q, [0]*q
for i in range(q):
    l, r = map(int, input().split())
    print(s[l-1:r].count("AC"))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
"""ナイーブ
for i in range(q):
    l, r = map(int, input().split())
    print(s[l-1:r].count("AC"))
"""
# 前処理＋全探索
# 区間なので累積和を疑う
t = [0]*n
count = 0
for i in range(n-1):
    t[i] = count
    if s[i] + s[i+1] == "AC":
        count += 1
    t[i+1] = count
#print(t)
for i in range(q):
    l, r = map(int, input().split())
    ans = t[r-1] - t[l-1]
    print(ans)
### BUGGY CODE ###

import sys
N = int(input())

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

numbers = []
for i in range(N):
    if a[i] not in numbers:
        numbers.append(a[i])
    elif a[i] in numbers:
        print('NO')
        sys.exit()
print('YES')

### FIXED CODE ###

import sys
N = int(input())

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

a.sort()

numbers = []
for i in range(N-1):
    if a[i] == a[i+1]:
        print('NO')
        sys.exit()
print('YES')
### BUGGY CODE ###

s = input()
ans = 0
for i in range(len(s) - 4):
    for j in range(i + 5, len(s) + 1):
        if int(s[i:j]) % 2019 == 0:
            ans += 1
print(ans)


### FIXED CODE ###

s = input()[::-1]
p = 0
dp = [0] * 2019
dp[0] = 1
d = 1
for i in s:    
    p = (int(i) * d + (p)) % 2019
    dp[p] += 1
    d *= 10
    d = d % 2019
ans = 0
for i in dp:
    ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

KMIN = 2
KMAX = 10 ** 12 + 1  # Exclusive

def main():
    n = int(input())
    k = []
    k += dividor_of(n - 1)
    for d in range(42):
        if d > 0:
            x = round(n ** (1.0 / d))
            if x ** d == n:
                k.append(x)
    k += eq72(n)
    k = sorted(x for x in k if x >= 2)
    print(len(set(k)))

def dividor_of(m):
    res = set()
    for i in range(1, 10 ** 6 + 1):
        if m % i == 0:
            res.add(i)
            res.add(m // i)
        if i ** 2 >= m:
            return sorted(list(res))

def eq72(n):
    res = []
    for k in range(2, 10 ** 6 + 1):
        for e in range(1, n // (k * k) + 2):
            for d in range(1, 42):
                if k ** d * (e * k + 1) > n:
                    break
                if k ** d * (e * k + 1) == n:
                    res.append(k)
    return res

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

KMIN = 2
KMAX = 10 ** 12 + 1  # Exclusive

def main():
    n = int(input())
    k = []
    k += dividor_of(n - 1)
    for d in dividor_of(n):
        if d < 2:
            continue
        x = n
        while x % d == 0:
            x //= d
        if x % d == 1:
            k.append(d)
    k = sorted(x for x in k if x >= 2)
    print(len(set(k)))

def dividor_of(m):
    res = set()
    for i in range(1, 10 ** 6 + 1):
        if m % i == 0:
            res.add(i)
            res.add(m // i)
        if i ** 2 >= m:
            return sorted(list(res))

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

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

import fractions
from functools import reduce

def gcd(numbers):
    return reduce(fractions.gcd, numbers)
ans = 0
for idx, num in enumerate(A):
  result = gcd(A[:idx:]+A[idx+1::])
  if result > ans:
    ans = result
print(ans)


### FIXED CODE ###

import fractions

N = int(input())
A = list(map(int, input().split()))
L = [0] * (N+1)
R = [0] * (N+2)
M = [0] * (N+1)

for i in range(1, N+1):
  L[i] = fractions.gcd(L[i-1], A[i-1])
  R[N-i+1] = fractions.gcd(R[N-i+2], A[N-i])

for i in range(1, N+1):
  M[i] = fractions.gcd(L[i-1], R[i+1])
print(max(M[1:]))
### BUGGY CODE ###

import numpy as sp
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
xy = sp.reshape(sp.array(xy), (n, 2))
def ABC075D(n, k, xy):
    x = xy[:, 0]
    y = xy[:, 1]
    Min = sp.inf
    for x1 in range(n-1):
        for x2 in range(x1+1, n):
            minx = min(x[x1], x[x2])
            maxx = max(x[x1], x[x2])
            for y1 in range(n-1):
                for y2 in range(y1+1, n):
                    count = 0
                    for i in range(n):
                        if minx <= x[i] <= maxx and min(y[y1], y[y2]) <= y[i] <= max(y[y1], y[y2]):
                            count += 1
                    if count == k:
                        Min = min(Min, abs((x[x1]-x[x2])*(y[y1]-y[y2])))
    print(Min)

ABC075D(n,k,xy)

### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

n = int(input())
l_a = list(map(int, input().split()))
many = []
for i in range(1, 100001) :
    many.append(l_a.count(i))
bef = sum(l_a)
q = int(input())
ans = []
for _ in range(q) :
    b, c = map(int, input().split())
    bef += (c - b)*many[b - 1]
    ans.append(bef)
    many[c - 1] += many[b - 1]
    many[b - 1] = 0

for value in ans :
    print(value)


### FIXED CODE ###

import collections

n = int(input())
l_a = list(map(int, input().split()))
col = collections.Counter(l_a)
bef = sum(l_a)
q = int(input())
ans = []
for _ in range(q) :
    b, c = map(int, input().split())
    bef += (c - b)*col[b]
    ans.append(bef)
    col[c] += col[b]
    col[b] = 0

for value in ans :
    print(value)
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	N,W=map(int,input().split())
	dp=[[0]*(W+1) for _ in range(N+1)]
	
	for i in range(N):
		w,v=map(int,input().split())
		for j in range(W):
			if j+1-w>=0:
				dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1],dp[i][j+1-w]+v)
			else:
				dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
			
	print(dp[-1][-1])
	
	
	
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	N,W=map(int,input().split())
	dp=[[0]*(W+1) for _ in range(N+1)]
	
	for i in range(N):
		w,v=map(int,input().split())
		for j in range(W):
			if j+1-w>=0:
				dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1],dp[i][j+1-w]+v)
			else:
				dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
			
	print(dp[-1][-1])
	
	
	
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

#! cat input | python3 main.py

n, k = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
    if a[0] == k:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    __import__("sys").exit()
a.sort()
ma = max(a)
def prim_fact(n):
    facts = []
    t = 2
    nn = n ** 0.5 + 1
    while True:
        if n % t == 0:
            facts.append(t)
            n //= t
        else:
            t += 1
        if t > n or t > nn:
            if n != 1:
                facts.append(n)
            break
    return facts


def f(a, k, ma):
    minv = float("inf")
    for i, v in enumerate(a[1:]):
        if v - a[i] != 0:
            minv = min(minv, v - a[i])
    minv = min(minv, a[0])

    sets = []
    setn = set()
    for v in a:
        s = set(prim_fact(v))
        sets.append(s)
        for i in s: setn.add(i)
    for v in setn:
        for s in sets:
            if v not in s:
                break
        else:
            minv = min(minv, v)
            break
    else:
        return False

    if minv == 1:
        return False

    a = a[:]
    for i in range(0, ma + minv, minv):
        if i == k:
            return False
        if i < a[0]:
            continue
        if i == a[0]:
            del a[0]
        else:
            return False
    return True

if ma < k:
    print("IMPOSSIBLE")
elif f(a, k, ma):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


### FIXED CODE ###

a, b = map(int, input().split())
array = list(map(int, input().split()))
impossible = "IMPOSSIBLE"
possible = "POSSIBLE"

array = list(set(array))

if len(array) == 1:
    if b == array[0]:
        print(possible)
    else:
        print(impossible)
    exit(0)

array.sort()

btw = [v1 - v2 for v1, v2 in zip(array[1:], array[0:])]
n = sorted(btw)[0]

same = len(set(btw)) == 1 or all([v % n == 0 for v in btw])

if b in array:
    print(possible)
elif array[-1] < b:
    print(impossible)
elif same and (b - array[0]) % n == 0:
    print(possible)
else:
    print(impossible)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(N // R + 1):
    N_R = N - i * R
    for j in range(N_R // G + 1):
        N_RG = N_R - j * G
        for k in range(N_RG // B + 1):
            N_RGB = N_RG - k * B
            if N_RGB == 0:
                ans += 1
print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(N // R + 1):
    for j in range((N - i * R) // G + 1):
        if (N - i * R - j * G) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res[::-1]

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

from collections import deque
import copy

h,w=map(int,input().split())
Inf=float('inf')
maze1=[]
for _ in range(h):
  s=list(input())
  for u in range(w):
    if s[u]=='.':
      s[u]=Inf
  maze1.append(s)
  
def maze_solve(maze,sy,sx,gy,gx):
  qu=deque([[sy,sx]])
  maze[sy][sx]=0
  
  while qu:
    y,x=qu.popleft()
    
    T=maze[y][x]
    for i in ([1,0],[-1,0],[0,1],[0,-1]):
      ny=y+i[0]
      nx=x+i[1]
      if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
        
        if maze[ny][nx]>T+1:
          maze[ny][nx]=T+1
          qu.append([ny,nx])
          
 
  return maze[gy][gx]
  

ans=-Inf
for i in range(h):
  for j in range(w):
    if maze1[i][j]!='#':
      for x in range(h):
        for y in range(w):
          if maze1[x][y]!='#':
            maze2=copy.deepcopy(maze1)
            
            ans=max(ans,maze_solve(maze2,i,j,x,y))
            
            
print(ans)
  

### FIXED CODE ###

from collections import deque
import copy

h,w=map(int,input().split())
Inf=float('inf')
maze1=[]
for _ in range(h):
  s=list(input())
  for u in range(w):
    if s[u]=='.':
      s[u]=Inf
  maze1.append(s)
  
def maze_solve(maze,sy,sx):
  qu=deque([[sy,sx]])
  maze[sy][sx]=0
  
  while qu:
    y,x=qu.popleft()
    
    T=maze[y][x]
    for i in ([1,0],[-1,0],[0,1],[0,-1]):
      ny=y+i[0]
      nx=x+i[1]
      if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
        
        if maze[ny][nx]>T+1:
          maze[ny][nx]=T+1
          qu.append([ny,nx])
          
  ans=-Inf
  for i in range(h):
    for j in range(w):
      if maze[i][j]!='#' and maze[i][j]!=Inf:
        ans=max(ans,maze[i][j])
  return ans
  

ans=-Inf
for i in range(h):
  for j in range(w):
    if maze1[i][j]!='#':
      maze2=copy.deepcopy(maze1)
      ans=max(ans,maze_solve(maze2,i,j))
            
            
print(ans)
### BUGGY CODE ###

N, Y = map(int, input().split())

ans = '-1 -1 -1'

count_max = Y / 1000  # all 1000
ans_list = []


for i in reversed(range(Y // 10000 + 1)):
    count_tmp1 = count_max - 9 * i
    price_tmp1 = Y - 10000 * i
    if count_tmp1 < N or price_tmp1 < 0:
        continue

    if count_tmp1 == N:
        ans = '{} {} {}'.format(i, 0, N - i)
        #ans_list.append(ans)
        break
    if price_tmp1 < 5000:
        continue

    is_continue = True
    for j in reversed(range(price_tmp1 // 5000 + 1)):
        count_tmp2 = count_tmp1 - 4 * j
        price_tmp2 = price_tmp1 - 5000 * j
        if count_tmp2 < N or price_tmp2 < 0:
            continue
        if count_tmp2 == N:
            ans = '{} {} {}'.format(i, j, N - i -j)
            # ans_list.append(ans)
            is_continue = False
            break
    if not is_continue:
        break
print(ans)

### FIXED CODE ###

N, Y = map(int, input().split())

count_max = Y / 1000  # all 1000

ans = '-1 -1 -1'
for i in range(N+1):  # 10000
    for j in range(N+1 - i):  # 5000
        k = N - i - j
        if k < 0:
            continue
        total = 10000 * i + 5000 * j + 1000 * k
        if total == Y:
            ans = '{} {} {}'.format(i, j, k)
            break
print(ans)
### BUGGY CODE ###

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

ans = 0
while n > a+b:
    ans += a
    n -= a+b

ans += min(n, a)
print(ans)

### FIXED CODE ###

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

ans = n // (a+b) * a
tmp = n % (a+b)
ans += min(a, tmp)

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

N = int(input())
A=[]
for i in range(N):
    A.append(int(input()))
counter = 0
for i in range(0, N):
    j = A[i] - 2
    if j == 0 or j == 1:
        counter += 1
    else:
        while j > 1:
            if A[i] % j == 0:
                break
            else:
                j -= 1
        else:
            counter += 1
            
print(counter)

### FIXED CODE ###

def isprime(x):
    import math
    if  x == 2:
        return True
    elif x < 2 or x % 2 == 0:
        return False
    else:
        i = 3
        while i <= math.sqrt(x):
            if x % i == 0:
                return False
            i += 2
        return True

N = int(input())
A=[]
for i in range(N):
    A.append(int(input()))
counter = 0
for i in range(0, N):
    if isprime(A[i]):
        counter += 1
        
print(counter)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in a:
    ans *= i
print("-1") if ans > 10**18 else print(ans)

### FIXED CODE ###

import sys

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
ans = 1
for i in a:
    if i == 0:
        print(0)
        sys.exit()
    ans *= i
    if ans > 10**18:
        print("-1")
        sys.exit()
print(ans)
### BUGGY CODE ###

from bisect import bisect_left as bl
from copy import deepcopy as dc
N = int(input())
Al = sorted(list(map(int, input().split())))
#print(Al)
q = -1
r = -1
for i in range(1, N - 1):
  A = dc(Al)
  #print(A)
  p = A.pop(0)
  temp = p ^ A[i]
  index = bl(A, temp)
  if index >= N - 1:
    continue
  if temp == A[index]:
    r = A.pop(i)
    q = A.pop(index)
    
    for j in range(1, N - 2):
      temp = q ^ r
      index = bl(A, temp)
      if temp == A[index]:
        t = r + 0
        if i == N - 4:
          r = p
        else:
          r = A.pop(index)
        q = t
      else:
        q = -1
        r = -1
        break
        
    
if q == -1:
  print("No")
  exit(0)
else:
  print("Yes")

### FIXED CODE ###

N = int(input())
Al = list(map(int, input().split()))
p = Al[0]
for i in range(1, N):
  p = p ^ Al[i]
if p == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

from collections import deque

H, W = map(int, list(input().split()))
Ch, Cw = map(int, list(input().split()))
Ch -= 1
Cw -= 1
Dh, Dw = map(int, list(input().split()))
Dh -= 1
Dw -= 1
S = [list(input()) for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw, 0])

while q:
    th, tw, t = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= t:
            continue
        seen[nh][nw] = t
        q.append([nh, nw, t])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= t + 1:
                continue
            seen[nh][nw] = t + 1
            q.append([nh, nw, t + 1])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh, Dw = map(int, input().split())
Dh -= 1
Dw -= 1
S = [input() for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw] + 1:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.appendleft([nh, nw])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])
### BUGGY CODE ###

# Problem D - Coloring Edges on Tree

from collections import deque

# input
N = int(input())
node_list = {} # 隣接リストの作成
color_count_list = [0]*(N+1)
ans_list = []
for i in range(N-1):
    a, b = map(int, input().split())
    if a in node_list:
        node_list[a].append(b)
    else:
        node_list[a] = [b]
    color_count_list[a] += 1
    color_count_list[b] += 1
    ans_list.append([a, b])

# initialization
color_list = [[0]*(N+1) for i in range(N+1)]
color_max_count = max(color_count_list)

# bfs search
visit_queue = deque([[-1, 1]]) # [[既に使った色], 遷移ノード]
while len(visit_queue)>0:
    p = visit_queue.popleft()

    used_color = p[0]
    if p[1] in node_list:
        nodes = node_list[p[1]]
        nodes_len = len(nodes)
        color_num = 1
        if nodes_len>=1:
            coloring_count = 0
            while coloring_count<nodes_len:
                if color_num==used_color:
                    color_num += 1
                    continue
                color_list[p[1]][nodes[coloring_count]] = color_num
                color_list[nodes[coloring_count]][p[1]] = color_num
                # queue insert
                visit_queue.append([color_num, nodes[coloring_count]])
                # color update
                coloring_count += 1
                color_num += 1

# output
print(color_max_count)
for a in ans_list:
    print(color_list[a[0]][a[1]])


### FIXED CODE ###

from collections import deque

n=int(input())
G=[[]for _ in range(n)]
L=[]
ans=[0]*n
for i in range(n-1):
   a,b=map(int,input().split())
   G[a-1].append(b-1)
   L.append(b-1)

que=deque([0])
while que:
   s=que.pop()
   color=1
   for ni in G[s]:
      if ans[s]==color:
         color+=1
      ans[ni]=color
      color+=1
      que.append(ni)
print(max(ans))
for i in L:
   print(ans[i])
### BUGGY CODE ###

import sys
import numpy as np
import bisect
if sys.platform in ['ios', 'win32', 'darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(x) for x in input().split()]

X = INT()

tmp = np.cumsum(range(X+1))

#print(tmp)
print(bisect.bisect_left(tmp, X))

### FIXED CODE ###

import sys
if sys.platform in ['ios', 'win32', 'darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(x) for x in input().split()]

X = INT()

# (1+n)*n = 2*X
print(round((X*2)**0.5))
### BUGGY CODE ###

from math import log2
n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
while a:
    m = a.pop()
    for i in range(int(log2(m))+2):
        k = 2**i - m
        if k in a:
            a.remove(k)
            ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
A = sorted(list(map(int, input().split())))[-1::-1]
c = Counter(A)
ans = 0
for a in A:
    b = (1<<a.bit_length()) - a
    if a == b and c[a] > 1:
        c[a] -= 2
        ans += 1
    elif a != b and c[a] > 0 and c[b] > 0:
        c[a] -= 1
        c[b] -= 1
        ans += 1
print(ans)
### BUGGY CODE ###

S=input()
N=len(S)

remainder=[0]*2019
S=list(map(int,list(S)))
S=S[::-1]
for i in range(N):
  S[i]=S[i]*(10**i)

val=0
for i in range(N):
  val+=S[i]
  remainder[val%2019]+=1

ans=remainder[0]
for i in range(2019):
  if remainder[i]<=1:
    continue
  else:
    ans+=remainder[i]*(remainder[i]-1)//2
print(ans)

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)