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

import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


N, Q = map(int, input().split())
ans = deque([0] * N)
con = deque([[] for _ in range(N)])

for _ in range(N - 1):
    p, c = map(int, input().split())
    con[p-1].append(c-1)
    con[c-1].append(p-1)

for _ in range(Q):
    p, v = map(int, input().split())
    ans[p-1] += v

stacks = deque()
stacks.append((0, -1))

while stacks:
    stack = stacks.pop()
    node, parent = stack[0], stack[1]

    children = con[node]
    for child in children:
        if child == parent:
            continue
        ans[child] += ans[node]
        stacks.append((child, node))

print(*ans)

### FIXED CODE ###

from collections import deque

N, Q = map(int, input().split())
edge = [[] for i in range(N)]
ops = []
ans = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
for _ in range(Q):
    ops.append(tuple(map(int, input().split())))

for op in ops:
    node = op[0] - 1
    pnt = op[1]
    ans[node] += pnt

stack = deque()
stack.append((0, -1))

while stack:
    st = stack.pop()
    node, parent = st[0], st[1]
    children = edge[node]
    for child in children:
        if child == parent:
            continue
        ans[child] += ans[node]
        stack.append((child, node))

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

from itertools import combinations_with_replacement

n = int(input())

calc = lambda x,y,z: x**2+y**2+z**2+x*y+y*z+z*x

def pattern(x,y,z):
   if x == y and y == z:
      return 1
   elif x == y or y == z or z == x:
      return 3
   elif x != y and y != z and z != x:
      return 6
   else:
      raise RuntimeError

def f(a):
   ans = 0
   nums = [i for i in range(1, a+1)]
   for x,y,z in combinations_with_replacement(nums, 3):
      if calc(x,y,z) == a:
         ans += pattern(x,y,z)
   return ans

for i in range(1, n+1):
   print(f(i))

### FIXED CODE ###

from itertools import combinations_with_replacement
from collections import defaultdict

n = int(input())

calc = lambda x,y,z: x**2+y**2+z**2+x*y+y*z+z*x

def pattern(x,y,z):
   if x == y and y == z:
      return 1
   elif x == y or y == z or z == x:
      return 3
   elif x != y and y != z and z != x:
      return 6
   else:
      raise RuntimeError

d = defaultdict(int)
n_ = int(pow(n, 0.5))
nums = [i for i in range(1, n_+1)]
for x,y,z in combinations_with_replacement(nums, 3):
   d[calc(x,y,z)] += pattern(x,y,z)
for i in range(1, n+1):
   print(d[i])
### BUGGY CODE ###

N,K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0]*N
for i in range(1,N):
    candidates = []
    for c in range(1, K+1):
        if i-c>=0:
            candidates.append(dp[i-c] + abs(h[i]-h[i-c]))
    dp[i] = min(candidates)
    #print(dp)
print(dp[-1])

### FIXED CODE ###

N,K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0]*N
for i in range(1,N):
    candidates = []
    for c in range(1, K+1):
        if i-c>=0:
            candidates.append(dp[i-c] + abs(h[i]-h[i-c]))
    dp[i] = min(candidates)
    #print(dp)
print(dp[-1])
### BUGGY CODE ###

n, m = map(int, input().split())

broken = []
for _ in range(m):
  broken.append(int(input()))
  
dp = [0] * (n + 1)

dp[0] = 1
if 1 not in broken:
  dp[1] = 1

for i in range(2, n + 1):
  if i - 1 not in broken:
    dp[i] += dp[i - 1]
  if i - 2 not in broken:
    dp[i] += dp[i - 2]
  dp[i] %= 1000000007
 
print(dp.pop())

### FIXED CODE ###

n, m = map(int, input().split())

safe = [True] * (n + 1)
for _ in range(m):
  safe[int(input())] = False
dp = [0] * (n + 1)

dp[0] = 1
if safe[1]:
  dp[1] = 1

for i in range(2, n + 1):
  if safe[i - 1]:
    dp[i] += dp[i - 1]
  if safe[i - 2]:
    dp[i] += dp[i - 2]
  dp[i] %= 1000000007
 
print(dp.pop())
### BUGGY CODE ###

n=int(input())
s=[input() for i in range(n)]
d={}
for i in range(n):
  d[s[i]] = d.get(s[i],0) + 1

max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
max_k_list.sort()
print(*max_k_list)

### FIXED CODE ###

from collections import Counter

n=int(input())
s=[input() for i in range(n)]

c = Counter(s)
c2 = c.most_common()
m = c2[0][1]#最大値
ans = [i[0] for i in c2 if i[1] == m]#回数が最大となるもの
ans.sort()
print(*ans)
### BUGGY CODE ###

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

b = []
tmp = 1

for i in range(n):
    tmp *= a[i]
    if i >= k:
        tmp //= a[i-k]
    if i >= k-1:
        b.append(tmp)

for i in range(1, len(b)):
    if b[i] > b[i-1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

for i in range(k, n):
    if a[i] > a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
l=[]
for i,x in enumerate(A):
    if len(l)>0:
        tmp=bisect.bisect_left(l,x)
        if tmp==0:l=[x]+l
        else:
            l[tmp-1]=x
    else:l.append(x)
print(len(l))

### FIXED CODE ###

import sys
import bisect
input=sys.stdin.readline

N=int(input())
A=[-int(input()) for _ in range(N)]
l=[A[0]]
for x in A[1::]:
    tmp=bisect.bisect(l,x)
    if tmp==len(l):l.append(x)
    else: l[tmp]=x
print(len(l))
### BUGGY CODE ###

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

### FIXED CODE ###

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

mod = 10 ** 9 +7
amount = sum(A)
calc = []
for i in range(N - 1):
  amount = amount - A[i]
  calc.append(amount)

for i in range(N - 1):
  calc[i] *= A[i]

print(sum(calc) % mod)
### BUGGY CODE ###

import sys
n = int(input())
s = []
s_num = []
for i in range(n):
  si = input()
  if not si in s:
    s.append(si)
    s_num.append(1)
  else:
    s_num[s.index(si)] += 1
maxs = []
m = max(s_num)
for j in range(len(s_num)):
  if s_num[j] == m:
    maxs.append(s[j])
maxs = sorted(maxs)
for ma in maxs:
  print(ma)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = []
for i in range(n):
  si = input()
  s.append(si)
  
C = Counter(s)
s_num = C.values()
m = max(s_num)
s_max = []
for k, v in C.items():
  if v == m:
    s_max.append(k)
s_max = sorted(s_max)
for sj in s_max:
  print(sj)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
N,W = map(int,input().split())
w = []
v = []
for i in range(N):
  w_,v_ = map(int,input().split())
  w.append(w_)
  v.append(v_)

dp = [[0]*(W+1) for _ in range(N+1)]

def memo(i,j):
  if dp[i][j]:
    return dp[i][j]
  if i == N:
    dp[i][j] = 0
  elif w[i] > j:
    dp[i][j] = memo(i+1,j)
  else:
    dp[i][j] = max(memo(i+1,j),memo(i+1,j-w[i])+v[i])
  return dp[i][j] 
print(memo(0,W))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
N,W = map(int,input().split())
w = []
v = []
for i in range(N):
  w_,v_ = map(int,input().split())
  w.append(w_)
  v.append(v_)

dp = [[0]*(W+1) for _ in range(N+1)]

def memo(i,j):
  if dp[i][j]:
    return dp[i][j]
  if i == N:
    dp[i][j] = 0
  elif w[i] > j:
    dp[i][j] = memo(i+1,j)
  else:
    dp[i][j] = max(memo(i+1,j),memo(i+1,j-w[i])+v[i])
  return dp[i][j] 
print(memo(0,W))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import itertools

# 標準入力の取得
N = int(input())
A = list(map(int, input().split()))

# 求解処理
# A_i + i = -A_j + j (i < j)
left = [A[i] + i for i in range(N)]
right = [-A[j] + j for j in range(N)]
result = 0
for i in range(N):
    result += right[i+1:].count(left[i])

# 結果出力
print(result)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import collections

# 標準入力の取得
N = int(input())
A = list(map(int, input().split()))

# 求解処理
# A_i + i = -A_j + j (i < j)
left = [A[i] + i for i in range(N)]
right = collections.Counter([-A[j] + j for j in range(N)])
result = 0
for l in left:
    result += right[l]

# 結果出力
print(result)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
INF = 10**9
dp = [0]*N
for i in range(1,N):
  m = INF
  for j in range(1,K+1):
    if i-j<0:
      break
    x = dp[i-j]+abs(h[i]-h[i-j])
    if m>x:
      m = x
  dp[i] = m
print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
INF = 10**9
dp = [0]*N
for i in range(1,N):
  m = INF
  for j in range(1,K+1):
    if i-j<0:
      break
    x = dp[i-j]+abs(h[i]-h[i-j])
    if m>x:
      m = x
  dp[i] = m
print(dp[-1])
### BUGGY CODE ###

n,m = map(int,input().split())
lst = []
for i in range(m):
  x,y = map(int,input().split())
  lst.append([x,y]) 
from collections import deque
d = ['t']*n
d[0] = 0
que = deque([1])
while que:
  p = que.popleft()
  for j in range(m):
    if lst[j][0] == p:
      q = lst[j][1]
      if d[q-1] == 't':
        d[q-1] = p
        que.append(q)
    if lst[j][1] == p:
      q = lst[j][0]
      if d[q-1] == 't':
        d[q-1] = p   
        que.append(q)
print('Yes')        
for i in range(1,n):
  print(d[i])
        

### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
a = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    a[x - 1].append(y - 1)
    a[y - 1].append(x - 1)
c = [0] * n
que = deque([])
que.append(0)
while len(que) > 0:
    e = que.popleft()
    for i in a[e]:
        if c[i] > 0:
            continue
        c[i] = e + 1
        que.append(i)
print("Yes")
for i in range(1, n):
    print(c[i])
### BUGGY CODE ###

import re
S = input()

cnt = 0
while True:
  s = re.sub('01|10', '', S, 1)
  if s != S:
    S = s
    cnt += 2
  else:
    print(cnt)
    exit()


### FIXED CODE ###

import re
S = input()

print(min(S.count('0'), S.count('1')) * 2)
### BUGGY CODE ###

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

ans = 2019
for i in range(l, r):
    for j in range(i+1, r + 1):
        temp = i * j % 2019
        if temp < ans:
            ans = temp
print(ans)


### FIXED CODE ###

import sys

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

ans = 2019
for i in range(l, r):
    for j in range(i+1, r + 1):
        temp = i * j % 2019
        if temp < ans:
            ans = temp
        if ans == 0:
            print(0)
            sys.exit()
print(ans)
### BUGGY CODE ###

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

ans=0
for i,a in enumerate(L):
  for j,b in enumerate(L[i+1:],start=i+1):
    for k,c in enumerate(L[j+1:],start=j+1):
      if a<b+c and b<c+a and c<a+b:
        ans+=1
print(ans)


### FIXED CODE ###

from bisect import bisect_left

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

for i in range(N-2):
  a=L[i]
  for j in range(i+1,N-1):
    b=L[j]
    ans+=bisect_left(L,a+b)-(j+1)
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
MAP = [list(input()) for _ in range(H)]
L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j] == "#":
            L[i][j] = 0
        elif j == 0:
            L[i][j] = 1
        else:
            L[i][j] = L[i] [j - 1] + 1

        if MAP[i][W - j - 1] == "#":
            R[i][W - j - 1] = 0
        elif j == 0:
            R[i][W - j - 1] = 1
        else:
            R[i][W - j - 1] = R[i][W - j] + 1

for j in range(W):
    for i in range(H):
        if MAP[i][j] == "#":
            U[i][j] = 0
        elif i == 0:
            U[i][j] = 1
        else:
            U[i][j] = U[i - 1][j] + 1

        if MAP[H - i - 1][j] == "#":
            D[H - i - 1][j] = 0
        elif i == 0:
            D[H - i - 1][j] = 1
        else:
            D[H - i - 1][j] = D[H - i][j] + 1
result = 0
for i in range(H):
    for j in range(W):
        result = max(result, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)

print(result)


### FIXED CODE ###

H, W = map(int, input().split())
MAP = [list(input()) for _ in range(H)]
L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j] == "#":
            L[i][j] = 0
        elif j == 0:
            L[i][j] = 1
        else:
            L[i][j] = L[i] [j - 1] + 1

        if MAP[i][W - j - 1] == "#":
            R[i][W - j - 1] = 0
        elif j == 0:
            R[i][W - j - 1] = 1
        else:
            R[i][W - j - 1] = R[i][W - j] + 1

for j in range(W):
    for i in range(H):
        if MAP[i][j] == "#":
            U[i][j] = 0
        elif i == 0:
            U[i][j] = 1
        else:
            U[i][j] = U[i - 1][j] + 1

        if MAP[H - i - 1][j] == "#":
            D[H - i - 1][j] = 0
        elif i == 0:
            D[H - i - 1][j] = 1
        else:
            D[H - i - 1][j] = D[H - i][j] + 1
result = 0
for i in range(H):
    for j in range(W):
        result = max(result, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)

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

import os, sys, re, math

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

s = [0 for i in range(N+1)]
for i in range(N):
    s[i+1] = ary[i] + s[i]

cnt = 0
for j in range(N,0,-1):
    for k in range(j,0,-1):
        if j == k:
            if s[j] % M == 0 and s[j] >= M:
                cnt += 1
        elif (s[j] - s[k]) % M == 0:
            cnt += 1
print(cnt)


### FIXED CODE ###

import os, sys, re, math

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

s = [0 for i in range(N+1)]
for i in range(N):
    s[i+1] = (ary[i] + s[i]) % M

m_map = {}

for j in range(0,N+1):
    if s[j] in m_map:
        m_map[s[j]] += 1
    else:
        m_map[s[j]] = 1

ret = 0
for i,v in m_map.items():
    if v >= 2:
        ret += v * (v-1) // 2
print(ret)
### BUGGY CODE ###

import math

x = int(input())

b = -100

while True:
    if x+b**5 > 0:
        if math.pow((x+b**5), 0.2).is_integer():
            print(int(math.pow((x+b**5), 0.2)), b)
            exit()
        
    b += 1

### FIXED CODE ###

x = int(input())

for i in range(-1000,1000):
    for j in range(-1000,1000):
        if i ** 5 - j ** 5 == x:
            print(i,j)
            quit()
### BUGGY CODE ###

N = int(input())
s = list(input() for _ in range(N))

l = list(map(sorted,s))
cnt = 0
for i in range(len(l)):
    for j in range(i+1,len(l)):
        #if(i != j):
            if(l[i] == l[j]):
                cnt += 1
print(cnt)

### FIXED CODE ###

d,a = {},0
for i in range(int(input())):
    k = ''.join(sorted(input()))
    d[k] = d.get(k,-1)+1
    a+= d[k]
print(a)
### BUGGY CODE ###

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    mod = 10**9+7
    a_sum = sum(A)
    ans = 0
    for i in range(len(A)-1):
        ans += A[i] * (a_sum - sum(A[:i+1])) % mod
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    mod = 10**9+7
    a_sum = sum(A)
    a_cum = [0] * (n+1)
    for i in range(n):
        a_cum[i + 1] = a_cum[i] + A[i]
    ans = 0
    for i in range(len(A)-1):
        ans += A[i] * (a_sum - a_cum[i+1]) % mod
        ans %= mod
    print(ans)

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

def main():
    class rolling_hash():
        def __init__(self, sequence):
            seq_size = len(sequence)  # 文字列の長さ
            self.Hash_0start = [0]*(seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            for i, j in enumerate(sequence):
                self.Hash_0start[i+1] = self.Hash_0start[i] + \
                    (j+1)*pow(3, i, mod)

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            return ((self.Hash_0start[r] - self.Hash_0start[l])
                    * pow(3, l*(mod-2), mod)) % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    mod = 2**61-1

    memo = [0]*n

    for k in range(32):
        a1 = [i % 2 for i in a]
        a1 += a1
        a2 = [i ^ 1 for i in a1]
        b_hash = rolling_hash([i % 2 for i in b]).calc_hash(0, n)
        a1 = rolling_hash(a1)
        a2 = rolling_hash(a2)
        for i, j in enumerate(memo):
            if j is None:
                continue
            elif a1.calc_hash(i, i+n) == b_hash:
                pass
            elif a2.calc_hash(i, i+n) == b_hash:
                memo[i] += 2**k
            else:
                memo[i] = None
        a = [i // 2 for i in a]
        b = [i // 2 for i in b]

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()


### FIXED CODE ###

def main():
    mod = 2**31-1
    pow3 = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        p = p*3 % mod
        pow3[i] = p

    def rolling_hash(seq):
        h = 0
        for i, j in enumerate(seq):
            h += (j+1)*pow3[i]
        h %= mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    def rolling_hash2(seq):
        p = 0
        p2 = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow3[i]
            p2 += (2-j)*pow3[i]
        return p % mod, p2 % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m = max(a+b)
    a1 = [0]*n
    b1 = [0]*n
    memo = [0]*n
    cnt = n
    pn = pow3[n]

    for k in range(len(bin(m))-2):
        k2 = 2**k
        for i, j in enumerate(a):
            a1[i] = (j & k2) >> k
        for i, j in enumerate(b):
            b1[i] = (j & k2) >> k
        b_hash, b_hash2 = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        for i, (j, k) in enumerate(zip(memo, A1)):
            if j is None:
                continue
            elif k == b_hash:
                pass
            elif k == b_hash2:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()
### BUGGY CODE ###

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

cnt=0
for i in range(N):
    if M>=2:    
        M    -= 2
        cnt  +=1

cnt += int(M/4)

print(cnt)

### FIXED CODE ###

N,M = map(int, input().split())
 
tmp=M-2*N

if tmp>=0:
    print(N+int(tmp/4))
else:
    print(int(M/2))
### BUGGY CODE ###

n, k = map(int,input().split())
P = list(map(int,input().split()))
S = []

for i in range(n-k+1):
    S.append(sum(P[i:i+k]))

print((max(S)+k)/2)

### FIXED CODE ###

from itertools import accumulate
n, k = map(int,input().split())
P = list(map(lambda x:(int(x)+1)/2,input().split()))
A = list(accumulate([0]+P))
B = []
for i in range(n-k+1):
    B.append(A[i+k]-A[i])

print(max(B))
### BUGGY CODE ###

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

for k in range(1, N):
  ans = 0
  for i in range(1, N+1):
    for j in range(i, N+1):
      dis = min(j-i, abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(j-X))
      if dis == k:
        ans += 1
  print(ans)

### FIXED CODE ###

N, X, Y = map(int, input().split())
dis = [0]*(N-1)

for i in range(1, N+1):
  for j in range(i+1, N+1):
    kyori = min(j-i, abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(j-X))
    dis[kyori-1] += 1
    
for ans in dis:
  print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
sa=set(a)
a2=[]
for ii in sa:
  ca=a.count(ii)
  a2.append([ii,ca])
  for jj in range(ca):
    a.remove(ii)
import numpy as np
a2=np.array(a2)
q=int(input())
for ii in range(q):
  b,c=map(int,input().split())
  idx=np.where(a2[:,0]==b)
  idx=np.append(idx,np.where(a2[:,0]==c))
  s=0
  for jj in idx:
    s+=a2[jj,1]
  a2=np.delete(a2,idx,axis=0)
  a2=np.append(a2,[[c,s]],axis=0)
  print(sum(a2[:,0]*a2[:,1]))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ma=10**5
a2=[0]*ma
for ii in a:
  a2[ii-1]+=1

def func(a2):
  r=0
  for jj in range(len(a2)):
     r+= a2[jj]*(jj+1)
  return r

r=func(a2)
q=int(input())
for ii in range(q):
  b,c=map(int,input().split())
  r+=(c-b)*a2[b-1]
  a2[c-1]+=a2[b-1]
  a2[b-1]=0
  print(r)
### BUGGY CODE ###

n,p=map(int,input().split())
ans=1
for i in range(int(pow(p,1/n)+1),0,-1):
    if(p%(i**n)==0):
        ans=i
        break
print(ans)        



### FIXED CODE ###

n,p=map(int,input().split())
root=round(p**(1/n))
for i in range(root,0,-1):
        if(p%(i**n)==0):
                print(i)
                break
### BUGGY CODE ###

N = int(input())
print(sum([i for i in range(N)]))


### FIXED CODE ###

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

from math import factorial
def comb(n,r):
  return factorial(n)//factorial(n-r)//factorial(r)
S=input()
N=len(S)
mod=[0 for i in range(2019)]
for i in range(N):
  s=S[i:N+1]
  mod2=int(s)%2019
  mod[mod2]+=1
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=comb(k,2)+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=comb(k,2)
print(ans)      

### FIXED CODE ###

import numpy as np
S=input()
N=len(S)
mod=[0 for i in range(2019)]
mod2=0
ten=1
for i in range(N-1,-1,-1): 
  s=int(S[i])*ten
  mod2+=np.mod(s,2019)
  mod2=np.mod(mod2,2019)
  mod[mod2]+=1
  ten=(ten*10)%2019
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
rng = 10100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
dp0 = [0 for i in range(n+1)]
dp1 = [0 for i in range(n+1)]
dp0[0] = 1
ans = 0
for i in range(1,k+1):
  x = a[i-1]
  if i%2:
    for j in range(n+1):
      for t in range(min(n-j,x)+1):
        dp1[j+t] = (dp1[j+t]+dp0[j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
    dp0 = [0 for i in range(n+1)]
  else:
    for j in range(n+1):
      for t in range(min(n-j,x)+1):
        dp0[j+t] = (dp0[j+t]+dp1[j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
    dp1 = [0 for i in range(n+1)]
if k%2:
  print(dp1[n])
else:
  print(dp0[n])

### FIXED CODE ###

n,k = map(int,input().split())
a = tuple(map(int,input().split()))
mod = 10**9+7
rng = 1001
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
  finv.append(pow(fctr[i],mod-2,mod))
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    if dp[i-1][j] == 0:
      continue
    y = dp[i-1][j]*fctr[n-j]*finv[n-x]%mod
    for t in range(min(n-j,x)+1):
      dp[i][j+t]=(dp[i][j+t]+y*fctr[n-t]*finv[n-j-t]*finv[t]*finv[x-t])%mod
print(dp[k][n])
### BUGGY CODE ###

def main():
	n=int(input())
	a=list(map(int, input().split()))
	count = 0
	while count==0:
		for i in range(n):
			if  a.count(a[i])> 1:
				count+=1
				print('NO')
				break
			else:
				continue
	if count==0:
		print('YES')
main()

### FIXED CODE ###

def main():
	n=int(input())
	a=list(map(int, input().split()))
	a.sort()
	c=0
	for i in range(n-1):
		if a[i] == a[i+1]:
			print('NO')
			c+=1
			break
	if c==0:
		print('YES')
main()
### BUGGY CODE ###

import bisect

n = int(input())
num = []
for i in range(n):
    a = int(input())
    temp = bisect.bisect_left(num, a)
    if temp == 0:
        num.append(a)
    else:
        num[temp - 1] = a
    num.sort()
print(len(num))

### FIXED CODE ###

import bisect, collections

n = int(input())
num = collections.deque([])
for i in range(n):
    a = int(input())
    temp = bisect.bisect_left(num, a)
    if temp == 0:
        num.appendleft(a)
    else:
        num[temp - 1] = a
print(len(num))