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

def main():
  import sys
  input = sys.stdin.readline

  N = int(input())
  S = input()

  ans = 0
  for i in range(N-1):
    for j in range(i+1,N):
      l = 0
      while(i+l < j and j+l < N and S[i+l] == S[j+l]):
        l += 1
      ans = max(l,ans)
  print(ans)

if __name__ == '__main__':
  main()

### FIXED CODE ###

def z_algo(S):
  N = len(S)
  A = [0]*N
  i = 1; j = 0
  A[0] = l = len(S)
  while i < l:
    while i+j < l and S[j] == S[i+j]:
      j += 1
    if not j:
      i += 1
      continue
    A[i] = j
    k = 1
    while l-i > k < j - A[k]:
      A[i+k] = A[k]
      k += 1
    i += k; j -= k
  return A

N = int(input())
S = input()

ans = 0
for i in range(N):
  SS = S[i:]
  Z = z_algo(SS)
  #print(Z)
  for j in range(1,len(SS)):
    if Z[j] > j:
      l = j
    else:
      l = Z[j]
    ans = max(l,ans)
print(ans)
### BUGGY CODE ###

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

num = a[0]
for i in range(1, len(a)):
  num *= a[i]

if(num > 10 ** 18):
  print(-1)
else:
  print(num) 


### FIXED CODE ###

import sys

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

a = sorted(a)

num = a[0]

for i in range(1, len(a)):
  num *= a[i]
  if(num == 0):
    print(0)
    sys.exit()
  if(num > 10 ** 18):
    print(-1)
    sys.exit()

print(num)
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 0
for i in range(N):
    s = P.count(P[i])
    t = P[i]
    if s > t:
        ans += 1
        P[i] = 0
    elif s < t:
        ans += 1
print(ans)

### FIXED CODE ###

import collections
N = int(input())
P = list(map(int,input().split()))
ans = 0
P.sort()
cnt = collections.Counter(P)
for i in cnt:
    s = cnt[i]
    if s > i:
        t =  s - i
        ans += t
    elif s < i:
        ans += s
print(ans)
### BUGGY CODE ###

n = int(input())

cnt = 1
for i in range(1,n+1):
    cnt *=i

print(cnt%(10**9+7))


### FIXED CODE ###

n = int(input())

cnt = 1
for i in range(1,n+1):
    cnt = (cnt*i)%(10**9+7)

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

N = int(input())
P = [int(x) for x in input().split()]
cnt=1
for i in range(1, N):
    if min(P[:i]) >= P[i]:
        cnt+=1
#         print(i, cnt)
        
print(cnt)

### FIXED CODE ###

N = int(input())
P = [int(x) for x in input().split()]
cnt=1
tmp=P[0]
for i in range(1, N):
    tmp = min(tmp, P[i-1])
    if tmp >= P[i]:
        cnt+=1
#         print(i, cnt)
        
print(cnt)
### BUGGY CODE ###

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

A = [A[i]-(i+1) for i in range(N)]

ans = 10 ** 9
#print (min(A))
for i in range(min(A), max(A)+1):
    b = [abs(A[j]-i) for j in range(N)]
#    print (sum(b))
#    print (b)
    ans = min(ans, sum(b))

print (ans)

### FIXED CODE ###

#平均値に近づけるという考え方が間違い-->中央値に近づける

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

A = [A[i]-(i+1) for i in range(N)]

A.sort()

center1 = A[N//2]
if N == 1:
    center2 = 10 ** 9
else:
    center2 = A[(N+2)//2]

ans1 = 0
for i in range(N):
    ans1 +=abs(A[i]-center1)
    
ans2 = 0
for j in range(N):
    ans2 += abs(A[j]-center2)
    
print (min(ans1, ans2))
### BUGGY CODE ###

h, w, m = list(map(int, input().split()))
count_row = [0 for _ in range(h)]
count_col = [0 for _ in range(w)]
# X = [[0 for i in range(w)] for _ in range(h)]
M = set()
for i in range(m):
    mh, mw = list(map(int, input().split()))
    # X[mh-1][mw-1] = 1
    M.add((mh-1, mw-1))
    # M[i] = [mh, mw]
    count_row[mh-1] += 1
    count_col[mw-1] += 1
max_row_index = [i for i, v in enumerate(count_row) if v == max(count_row)]
max_col_index = [i for i, v in enumerate(count_col) if v == max(count_col)]
ans = max(count_row) + max(count_col) -1

if len(max_col_index)*len(max_row_index) > m:
    ans += 1
else:
    flag = False
    for i in max_row_index:
        for j in max_col_index:
            if (i, j) not in M:
                ans += 1
                flag = True
                break
        if flag:
            break

print(ans)


### FIXED CODE ###

h, w, m = list(map(int, input().split()))
count_row = [0 for _ in range(h)]
count_col = [0 for _ in range(w)]
# X = [[0 for i in range(w)] for _ in range(h)]
max_col = 0
max_row = 0
max_row_index = []
max_col_index = []
M = set()
for i in range(m):
    mh, mw = list(map(int, input().split()))
    # X[mh-1][mw-1] = 1
    M.add((mh-1, mw-1))
    count_row[mh-1] += 1
    count_col[mw-1] += 1
    if count_row[mh-1] > max_row:
        max_row = count_row[mh-1]
        max_row_index = [mh-1]
    elif count_row[mh-1] == max_row:
        max_row_index.append(mh-1)
    
    if count_col[mw-1] > max_col:
        max_col = count_col[mw-1]
        max_col_index = [mw-1]
    elif count_col[mw-1] == max_col:
        max_col_index.append(mw-1)
# max_row_index = [i for i, v in enumerate(count_row) if v == max(count_row)]
# max_col_index = [i for i, v in enumerate(count_col) if v == max(count_col)]
# ans = max(count_row) + max(count_col) -1
ans = max_col + max_row -1

if len(max_col_index)*len(max_row_index) > m:
    ans += 1
else:
    flag = False
    for i in max_row_index:
        for j in max_col_index:
            if (i, j) not in M:
                ans += 1
                flag = True
                break
        if flag:
            break
print(ans)
### BUGGY CODE ###

N=int(input())
S = [input() for i in range(N)]
P={}
A=[]
for i in range(len(S)):
    P[S[i]] = 0
    for j in range(len(S)):
        if S[i]==S[j]:
            P[S[i]] += 1

m=P[S[0]]
for k in range(len(S)):
    if m<P[S[k]]:
        m=P[S[k]]

for k in range(len(S)):
    if P[S[k]]==m:
        A.append(S[k])

A0=set(A)
A1=list(A0)
A1.sort()

for List in A1:
    print(List)

### FIXED CODE ###

import collections
N=int(input())
S = [input() for i in range(N)]
A=[]

P=collections.Counter(S)

y=max(P.values())
A = [k for k, v in P.items() if v == y]

A.sort()

for List in A:
    print(List)
### BUGGY CODE ###

import sys
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n, m = nm()
ans = 1
for i in range(2, m + 1):
    if i * n > m:
        break
    if m % i == 0 and m // i >= n:
        ans = max(ans, i)
print(ans)


### FIXED CODE ###

import sys
import math
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n, m = nm()
ans = 1
for i in range(1, int(math.sqrt(m)) + 2):
    if m % i == 0:
        if m // i >= n and i >= n:
            ans = max(ans, i, m // i)
        elif m // i >= n:
            ans = max(ans, i)
        elif i >= n:
            ans = max(ans, m // i)
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
ans = []
if n % 2 == 0:
    for i in range(n):
        if i % 2 == 1: ans.insert(0, a[i])
        else: ans.append(a[i])
else:
    ans.append(a[0])
    for i in range(1, n):
        if i % 2 == 1: ans.append(a[i])
        else: ans.insert(0, a[i])
print(*ans)

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
ans = []
if n == 1: print(a[0])
else:
    for i in a[::-2]:
        ans.append(i)
    if n % 2 == 0:
        for i in a[::2]:
            ans.append(i)
    else:
        for i in a[1::2]:
            ans.append(i)
print(*ans)
### BUGGY CODE ###

h,w,k = map(int,input().split())

honsu=w


a = 0
def amida(h,w):
  global a
  if h == 0 and w == k:
    return 1
  if h ==0:
    return 0
  if not(1<=w<=honsu):
    return 0
  com1 = fib(honsu-w+1)*fib(w-1)*amida(h-1,w-1)
  com2 = fib(honsu-w+1)*fib(w)*amida(h-1,w) 
  com3 = fib(honsu-w)*fib(w)*amida(h-1,w+1)   
  
  return com1+com2+com3
  
fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]

print(amida(h,1)%1000000007)

### FIXED CODE ###

h,w,k = map(int,input().split())

a=[[0]*w for i in range(h+1)]

fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]
  

for j in range(w):
  a[0][j]=0
a[0][0]=1

for i in range(1,h+1):
  for j in range(w):
    if w==1:
      a[i][j]=a[i-1][j]
    elif j==0:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j+1]*fib(w-1)
    elif 1<=j<w-1:
      a[i][j]=a[i-1][j-1]*fib(w-j)*fib(j)+a[i-1][j]*fib(w-j)*fib(j+1)+a[i-1][j+1]*fib(w-j-1)*fib(j+1)
    elif j==w-1:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j-1]*fib(w-1)
print(a[h][k-1]%1000000007)
### BUGGY CODE ###

N,A,B = [int(i) for i in input().split()]

rcnt = 0
bcnt = 0
while True:
    if bcnt + rcnt + A >= N:
        bcnt += N-(bcnt+rcnt)
        break
    else:
        bcnt += A
        
    if bcnt + rcnt + B >= N:
        rcnt += N-(bcnt+rcnt)
        break
    else:
        rcnt += B

print(bcnt)

### FIXED CODE ###

N,A,B = [int(i) for i in input().split()]

bcnt = 0
cnt = N // (A+B)

bcnt += cnt*A
rest = N - (A+B)*cnt

bcnt += min(A, rest)

print(bcnt)
### BUGGY CODE ###

S = input()

L = 0
for i in range(len(S)+1):
  for j in range(len(S)+1):
    if i<j:
      if int(S[i:j])>2018:
        if int(S[i:j])%2019==0:
          L += 1
print(L)

### FIXED CODE ###

S = input()[::-1]
n = len(S)

cnt = [0] * 2019
cnt[0] = 1
m = 0
d = 1
for i in S:
  m += int(i) * d
  m %= 2019
  cnt[m] += 1
  d *= 10
  d %= 2019

ans=0
for i in cnt:
  ans += int(i*(i-1)/2)
print(ans)
### BUGGY CODE ###

import numpy as np
from itertools import combinations
N = int(input())
A = np.array(list(map(int, input().split())), dtype= int)
X = A.sum()
A1 = np.cumsum(A)
mincost1 = -1
for r2 in range(1,N-2):
    Y = A1[r2]
    mincost2 = -1
    r1 = 1
    for i in range(0,r2):
        L = A1[i]
        R = Y - L
        cost = np.abs(R-L)
        if mincost2 < 0 or mincost2 >  cost:
            mincost2 = cost
            r1 = i
    P = A1[r1]
    Q = Y - A1[r1]

    mincost3 = -1
    r3 = N-1
    for i in range(r2+1,N):
        L = A1[i] - Y
        R = X - Y - L
        cost = np.abs(R-L)
        if mincost3 < 0 or mincost3 >  cost:
            mincost3 = cost
            r3 = i

    R = A1[r3]-Y
    S = X-A1[r3]
    cost = max(P,Q,R,S) - min(P,Q,R,S)
    if mincost1 < 0 or mincost1 >  cost:
            mincost1 = cost
print(mincost1)


### FIXED CODE ###

from itertools import accumulate
input()
*s, = accumulate(map(int, input().split()))
l,r,t = 0,2,s[-1]
c = t
for m in s[1:-2]:
    while t+m > s[r]+s[r+1]:
        r += 1
    while m > s[l]+s[l+1]:
        l += 1
    x = sorted([s[l],m-s[l],s[r]-m,t-s[r]])
    c = min(c,x[-1]-x[0])
print(c)
### BUGGY CODE ###

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

cnt = 0
for r in range(0,N//R+1):
    for g in range(0,(N-R*r)//G+1):
        if (N - (R*r + G*g)) % B == 0 and N - (R*r + G*g) >= 0:
            #print(r,g,(N-r-g))
            cnt += 1

print(cnt)

### FIXED CODE ###

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

cnt = 0
for r in range(0,N//R+1):
    for g in range(0,(N-R*r)//G+1):
        if (N - R*r - G*g) % B == 0 :
            #print(r,g,(N-r-g))
            cnt += 1

print(cnt)
### BUGGY CODE ###

N = int(input())
pow = 1
for i in range(1,N+1):
        pow = pow*i
num = 10**9+7
print(pow%num)

### FIXED CODE ###

N = int(input())
pow = 1
num = 10**9+7
for i in range(1,N+1):
        pow = pow*i%num
print(pow%num)
### BUGGY CODE ###

from collections import Counter
import sys

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))

if n < m:
    print('NO')
else:
    for i in range(m):
        if i!=m-1:
            if t[i]==t[i+1]:
                continue
            else:
                if t.count(t[i])>d.count(t[i]):
                    print('NO')
                    sys.exit()
        else:
            if t.count(t[i])>d.count(t[i]):
                print('NO')
                sys.exit()
            
    print('YES')

### FIXED CODE ###

import collections
import sys

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))

ct=collections.Counter(t)
cd=collections.Counter(d)
cct=list(ct.items())
#print(cc)
if n < m:
    print('NO')
else:
    for i in range(len(cct)):
        if cd[cct[i][0]]<cct[i][1]:
            print('NO')
            sys.exit()
    print('YES')
### BUGGY CODE ###

from collections import Counter as counter
from sys import stdin 

N = int(stdin.readline().rstrip())
strings = ''
lists = []
for _ in range(N):
  s = ''.join(sorted(stdin.readline().rstrip()))
  strings += s
  lists.append(s)
counts = [strings[(i+1)*len(s):].count(c) for i, c in enumerate(lists)]
match_count = sum(counts)
print(match_count)

### FIXED CODE ###

N = int(input())
dic = {}
count = 0
for _ in range(N):
  s = ''.join(sorted(input()))
  if s in dic.keys():
    count += dic[s]
    dic[s] += 1
  else:
    dic[s] = 1
print(count)
### BUGGY CODE ###

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

costs = [0] * N
for i in range(1,N):
  s = max(i-K, 0)
  mn = float('inf')
  for a,b in zip(costs[s:i],h[s:i]):
    cur = a + abs(h[i]-b)
    if cur < mn:
      mn = cur
 
  costs[i] = mn
print(costs[-1])

### FIXED CODE ###

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

def aa (n,k,ll):
  dp = [0] * n
  for i in range(1,n):
    s = max(i-k,0)
    mn = float('inf')
    for a,b in zip(dp[s:i],ll[s:i]):
      cur = a + abs(ll[i]-b)
      if cur < mn:
        mn = cur
  
    dp[i] = mn
  print(dp[-1])

aa(N,K,h)
### BUGGY CODE ###

str=input()
count=0
for i in range(0,len(str)-3):
    for j in range(4,len(str)-i+1):
        if float(str[i:j+i])%2019==0:
            count=count+1
            if j+4>len(str):
                break
            else:
                j=j+3
print(count)

### FIXED CODE ###

s=input()
b=[0]*2019
b[0]=1
now=0
m=2019
c=1
ans=0
for i in range(len(s)-1,-1,-1):
    now+=int(s[i])*c
    now=now%m
    c=c*10
    ans=ans+b[now]
    b[now]=b[now]+1
    c=c%m

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

n, q = [int(i) for i in input().split()]
s = input()
positions = []

for i in range(1, n+1):
    if s[(i-1):(i+1)] == 'AC':
        positions.append(i)

for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(len([i for i in positions if i in range(l, r)]))


### FIXED CODE ###

import bisect

n, q = [int(i) for i in input().split()]
s = input()
positions = []

for i in range(1, n+1):
    if s[(i-1):(i+1)] == 'AC':
        positions.append(i)

for i in range(q):
    l, r = [int(i) for i in input().split()]
    l_index = bisect.bisect_left(positions, l)
    r_index = bisect.bisect_left(positions, r)
    print(r_index - l_index)
### BUGGY CODE ###

# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
P = lr()
dp = [[min(i, N-1-i)] * N for i in range(N)]
people = [[True] * N for i in range(N)]
for j in range(N):
    x = min(j, N-1-j)
    for i in range(N):
        dp[i][j] = min(dp[i][j], x)

answer = 0

def bfs(sy, sx):
    que = deque([(sy, sx)])
    popleft = que.popleft; append = que.append
    while que:
        y, x = popleft()
        if (y, x) in used:
            continue
        used.add((y, x))
        cur = dp[y][x]
        if cur == -1 and not people[y][x]:
            people[y][x] = True
        for dy, dx in zip([0, 1, 0, -1], [1, 0, -1, 0]):
            ny = y + dy
            nx = x + dx
            if 0 <= ny < N and 0 <= nx < N:
                if dp[ny][nx] > cur + 1:
                    dp[ny][nx] = cur + 1
                    if not people[ny][nx]:
                        dp[ny][nx] = cur
                    append((ny, nx))
                elif dp[ny][nx] > cur and (not people[ny][nx]):
                    # 人がいない時
                    dp[ny][nx] = cur
                    append((ny, nx))

for p in P:
    p -= 1
    i = p // N
    j = p % N
    answer += dp[i][j]
    dp[i][j] -= 1
    people[i][j] = False
    used = set()

    bfs(i, j)

print(answer)


### FIXED CODE ###

# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    N = ir()
    P = lr()
    P = [((p-1)//N, (p-1)%N) for p in P]
    dp = [[min(i, N-1-i, j, N-1-j) for j in range(N)] for i in range(N)]
    people = [[True] * N for i in range(N)]

    answer = 0
    for i, j in P:
        answer += dp[i][j]
        people[i][j] = False
        que = deque([(i, j, dp[i][j])])
        popleft = que.popleft; append = que.append
        while que:
            y, x, cur = popleft()
            cur += people[y][x]
            if x > 0:
                if dp[y][x-1] > cur:
                    dp[y][x-1] = cur
                    append((y, x-1, cur))
            if x < N-1:
                if dp[y][x+1] > cur:
                    dp[y][x+1] = cur
                    append((y, x+1, cur))
            if y > 0:
                if dp[y-1][x] > cur:
                    dp[y-1][x] = cur
                    append((y-1, x, cur))
            if y < N-1:
                if dp[y+1][x] > cur:
                    dp[y+1][x] = cur
                    append((y+1, x, cur))

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

import sys
sys.setrecursionlimit(10**7)
MOD = 10**9+7

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

lim = 10**7
fact = [1, 1] + [0] * (lim-1)
fact_inv = [1, 1] + [0] * (lim-1)
inv = [0, 1] + [0] * (lim-1)
for i in range(2, lim+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD//i) % MOD
    fact_inv[i] = fact_inv[i-1] * inv[i] % MOD
def comb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact[n] * (fact_inv[m] * fact_inv[n-m] % MOD) % MOD

dp = [1] * n
size = [0] * n

def dfs(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        dfs(nv, v)
        ns = size[nv]+1
        size[v] += ns
        dp[v] *= dp[nv] * comb(size[v], ns) % MOD
        dp[v] %= MOD

def dfs2(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        d, sz = dp[v], size[v]
        d *= inv[dp[nv]] * inv[comb(sz, size[nv]+1)] % MOD
        d %= MOD
        sz -= size[nv]+1

        size[nv] += sz+1
        dp[nv] *= d * comb(size[nv], sz+1) % MOD
        dp[nv] %= MOD
        dfs2(nv, v)

dfs(0, -1)
dfs2(0, -1)
print(*dp, sep="\n")


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().rstrip()
MOD = 10**9+7

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

lim = 10**5*2
fact = [1, 1] + [0] * (lim-1)
fact_inv = [1, 1] + [0] * (lim-1)
inv = [0, 1] + [0] * (lim-1)
for i in range(2, lim+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD//i) % MOD
    fact_inv[i] = fact_inv[i-1] * inv[i] % MOD
def comb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact[n] * (fact_inv[m] * fact_inv[n-m] % MOD) % MOD
def icomb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact_inv[n] * (fact[m] * fact[n-m] % MOD) % MOD

dp = [1] * n
size = [0] * n

def dfs(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        dfs(nv, v)
        ns = size[nv]+1
        size[v] += ns
        dp[v] *= dp[nv] * comb(size[v], ns) % MOD
        dp[v] %= MOD

def dfs2(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        d, sz = dp[v], size[v]
        d *= pow(dp[nv], MOD-2, MOD) * icomb(sz, size[nv]+1) % MOD
        d %= MOD
        sz -= size[nv]+1

        size[nv] += sz+1
        dp[nv] *= d * comb(size[nv], sz+1) % MOD
        dp[nv] %= MOD
        dfs2(nv, v)

dfs(0, -1)
dfs2(0, -1)
print(*dp, sep="\n")
### BUGGY CODE ###

n =int(input())
s = list(map(int,input().split()))
i = 1
l =[]
while i <= n:
     l.append(s.count(i))
     i += 1
[print(_) for _ in l]

### FIXED CODE ###

n =int(input())
s = list(map(int,input().split()))
l =[0]*n
i = 0
while i < n-1 :
     l[s[i]-1] += 1
     i += 1
for _ in range(n):
     print(l[_])
### BUGGY CODE ###

def q_C(N, arrA):
	res = [0] * N
	#sortA = sorted(arrA, reverse=True)
	for i in range(N):
		tmp = i + 1
		for j in range(N):
			if tmp == arrA[j]:
				res[i] = j + 1
				break
	print(*res)

N = int(input())
arrA = [int(x) for x in input().split()]
q_C(N, arrA)


### FIXED CODE ###

def q_C(N, arrA):
	res = [0] * N
	for i in range(N):
		res[arrA[i] - 1] = i + 1
	print(*res)

N = int(input())
arrA = [int(x) for x in input().split()]
q_C(N, arrA)
### BUGGY CODE ###

def main():
    N, T = map(int, raw_input().split())
    t = map(int, raw_input().split())
    c = t[-1] + T + 1
    a = [0 for _ in xrange(c)]
    for i in t:
        a[i] += 1
        a[i+T] -= 1

    count = 0
    for i in xrange(c):
        if(0 < i):
            a[i] += a[i - 1]
            if(a[i] != 0): count += 1

    if(a[0] != 0): count += 1
    print count
    return 0

if __name__ == '__main__':
    main()

### FIXED CODE ###

n, t = map(int, input().split())
T = list(map(int, input().split()))

ans = t
for t1, t2 in zip(T[:-1], T[1:]):
  ans += min(t2 - t1, t)

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

import sys
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
V = [[] for _ in range(N)]
X = [0 for _ in range(N)]

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

for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    X[p] += x
# p親、n現在、s合計
def dfs(p, n, s):
    X[n] += s
    for i in V[n]:
        if i == p:
            continue
        else:
            dfs(n, i, X[n])
dfs(-1,0,0)
for i in range(N):
    print(X[i], end=" ")
        

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
 
n , q = map(int,input().split())
point = [0] * n
edge = [[] for i in range(n)]
 
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
 
for _ in range(q):
    a , b = map(int,input().split())
    point[a-1] += b
 
def dfs(now, last=-1):
    for nxt in edge[now]:
        if nxt==last: continue
        point[nxt] += point[now]
        dfs(nxt, now)
dfs(0)
print(*point)
### BUGGY CODE ###

n=int(input())
s=[input() for _ in range(n)]
ans=0
for i in range(n):
    lst=sorted(list(s[i]))
    for j in range(i+1,n):
        lst1=sorted(list(s[j]))
        if lst==lst1:
            ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
ans=0
dic={}
for _ in range(n):
    s=input()
    s=sorted(s)
    s=''.join(s)
    if not s in dic.keys():
      dic[s]=1
    else: dic[s]+=1
for i in dic.values():
  ans+=i*(i-1)//2


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

from sys import stdin


def get_result(data):
    N, K = data
    mod = 10**9+7
    value = [i for i in range(N+1)]
    ans = 0
    for r in range(K, N+2):
        min_val = sum(value[:r])
        max_val = sum(value[-r:])
        ans += (max_val - min_val + 1) % mod
    return ans % mod


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin


def get_result(data):
    N, K = data
    mod = 10**9+7
    e_val = [i for i in range(N+1)]
    # 累積和を使ってsumを計算
    e_cumsum = [0]
    for i in range(N+1):
        e_cumsum.append(e_cumsum[i] + e_val[i])
    ans = 0
    for r in range(K, N+2):
        min_val = e_cumsum[r]
        max_val = e_cumsum[N+1] - e_cumsum[N+1-r]
        ans += (max_val - min_val + 1) % mod
    return ans % mod


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)