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

import sys

N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
        w[i], v[i] = map(int, sys.stdin.readline().split())

#WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]


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

for i in range(1, W+1):
        for j in range(1, N+1):
                if i - w[j-1]>=0:
                #if i - WV[j-1][0]>=0:
                        dp[i][j] = max(dp[i-w[j-1]][j-1]+v[j-1], dp[i][j-1])
                        #dp[i][j] = max(dp[i-WV[j-1][0]][j-1]+WV[j-1][1], dp[i][j-1])
                else:
                        dp[i][j] = dp[i][j-1]

print(dp[W][N])

### FIXED CODE ###

import sys
 
N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
        w[i], v[i] = map(int, sys.stdin.readline().split())
 
#WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
 
 
dp = [[0]*(N+1) for j in range(W+1)]
 
for i in range(1, W+1):
        for j in range(1, N+1):
                if i - w[j-1]>=0:
                #if i - WV[j-1][0]>=0:
                        dp[i][j] = max(dp[i-w[j-1]][j-1]+v[j-1], dp[i][j-1])
                        #dp[i][j] = max(dp[i-WV[j-1][0]][j-1]+WV[j-1][1], dp[i][j-1])
                else:
                        dp[i][j] = dp[i][j-1]
 
print(dp[W][N])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

N,Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #頂点を0indexに
  G[a].append(b);G[b].append(a)
#query = {}
ans = [0 for _ in range(N)]
for i in range(Q):
  p,x = map(int,input().split())
  p-=1
  ans[p] += x

def dfs(v,par): #vが今いる頂点、parが親。
  for u in G[v]:
    if u != par:
      ans[u] += ans[v]
      dfs(u,v)
dfs(0,-1)
print(*ans)
  
  

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

N,Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #頂点を0indexに
  G[a].append(b);G[b].append(a)
#query = {}
ans = [0 for _ in range(N)]
for i in range(Q):
  p,x = map(int,input().split())
  p-=1
  ans[p] += x

def dfs(v,par): #vが今いる頂点、parが親。
  if par != -1:
    ans[v] += ans[par]
  for u in G[v]:
    if u != par:
      dfs(u,v)
dfs(0,-1)
print(*ans)
### BUGGY CODE ###

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

ans = 1
for i in An:
    ans *= i

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

### FIXED CODE ###

def Multiplication_2():
    N = int(input())
    An = list(map(int,input().split()))

    if 0 in An:
        return 0
    
    over = 10 ** 18

    ans = 1
    
    for i in An:
        ans *= i
        if ans > over:
            return -1
        #print(ans)
    
    return ans

print(Multiplication_2())
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
C = list(map(int, input().split()))
LRST = []
for i in range(Q):
    l, r = map(int, input().split())
    LRST.append((l-1, 0, r-1, i))


class FenwickTree(object):
    def __init__(self, n):
        self._bit = [0] * (n+1)
        self.n = n+1
    
    def add(self, i, a):
        i += 1
        while i < self.n:
            self._bit[i] += a
            i += i & -i
    
    def sum(self, i):
        i += 1
        ret = 0
        while i > 0:
            ret += self._bit[i]
            i -= i & -i
        return ret


def solve():
    memo = [-1] * N
    for i, c in enumerate(C):
        if memo[c-1] >= 0:
            LRST.append((memo[c-1], 1, i, -1))
        memo[c-1] = i
    LRST.sort(reverse=True)
    ans =[0 for _ in range(Q)]
    ft = FenwickTree(N+1)
    for sl, typ, tr, q in LRST:
        if typ == 1:
            ft.add(tr, 1)
        else:
            ans[q] = tr - sl + 1 - ft.sum(tr)
    for a in ans:
        print(a)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(Q):
    l, r = map(int, input().split())
    LR.append((l-1, r-1, i))


class FenwickTree(object):
    def __init__(self, n):
        self._bit = [0] * (n+1)
        self.n = n+1
    
    def add(self, i, a):
        i += 1
        while i < self.n:
            self._bit[i] += a
            i += i & -i
    
    def sum(self, i):
        i += 1
        ret = 0
        while i > 0:
            ret += self._bit[i]
            i -= i & -i
        return ret


def solve():
    memo = [-1] * N
    ST = []
    nst = 0
    for i, c in enumerate(C[::-1]):
        if memo[c-1] >= 0:
            ST.append((N-i-1, memo[c-1]))
            nst += 1
        memo[c-1] = N-i-1
    # ST.sort(reverse=True)
    LR.sort(reverse=True, key=lambda x:x[0])
    ans =[0 for _ in range(Q)]
    ft = FenwickTree(N+1)
    j = 0
    for l, r, i in LR:
        while j < nst and ST[j][0] >= l:
            ft.add(ST[j][1], 1)
            j += 1
        ans[i] = r - l + 1 - ft.sum(r)
    return ans

if __name__ == "__main__":
    print('\n'.join(map(str, solve())))
### BUGGY CODE ###

n = int(input())
l = sorted(list(map(int,input().split())))
ans = 0
import bisect
for i in range(n):
    for j in range(i+1,n):
        a1 = abs(l[i]-l[j])
        a2 = l[i]+l[j]
        x1 = bisect.bisect_right(l,a1)
        x2 = bisect.bisect_left(l,a2)
        buf = 0
        if x1<=i<=x2:buf+=1
        if x1<=j<=x2:buf+=1
        ans += max(0,x2-x1-buf)
print(ans//3)


### FIXED CODE ###

n = int(input())
l = sorted(list(map(int,input().split())))
ans = 0
import bisect
for i in range(n):
    for j in range(i+1,n):
        a = l[i]+l[j]
        x = bisect.bisect_left(l,a)
        if x>j:
            ans += max(0,x-j-1)
print(ans)
### BUGGY CODE ###

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

    B = [(A[i], i) for i in range(N)]
    B.sort(key = lambda x: x[0], reverse = True)

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

    for i, b in enumerate(B):
        a = b[0]
        tmp = b[1]
        for x in range(i + 1):
            DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
            DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

    ans = 0
    for i in range(N + 1):
        ans = max(ans, DP[i][N - i])

    print (ans)

    # for tmp in DP:
    #     print (tmp)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

B = [(A[i], i) for i in range(N)]
B.sort(key = lambda x: x[0], reverse = True)

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

for i in range(N):
    a = B[i][0]
    tmp = B[i][1]
    for x in range(i + 1):
        DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
        DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

ans = 0
for i in range(N + 1):
    ans = max(ans, DP[i][N - i])

print (ans)

# for tmp in DP:
#     print (tmp)
### BUGGY CODE ###

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

a_2 = [0 for i in range(n)]
for i in range(n):
    a_2[a[i]-1] += 1

al = [0 for i in range(n)]
c = 0
for i in a_2:
    al[c] += int(i * (i-1) / 2)
    c += 1

for i in range(n):
    f = a[i]
    t = a_2[f-1] - 1
    print(int(sum(al)-(al[f-1]-t*(t-1)/2)))
    


### FIXED CODE ###

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

a_2 = [0 for i in range(n)]
for i in range(n):
    a_2[a[i]-1] += 1

al = [0 for i in range(n)]
c = 0
for i in a_2:
    if i > 1:
        al[c] += i * (i-1) / 2
    c += 1

sine = sum(al)
for i in range(n):
    f = a[i]
    t = a_2[f-1] - 1
    print(int(sine-(al[f-1]-t*(t-1)/2)))
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
A.sort()


# print(A)
t = 0
for k in range(1, n):
    # print("A[0:{}]={}".format(k, A[:k]))
    # print("{} <? {}".format(2 * sum(A[:k]), A[k]))
    if 2 * sum(A[:k]) < A[k]:
        t = max(t, k)

print(n - t)



### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
A.sort()


# print(A)
# t = 0
# for k in range(1, n):
#     # print("A[0:{}]={}".format(k, A[:k]))
#     # print("{} <? {}".format(2 * sum(A[:k]), A[k]))
#     if 2 * sum(A[:k]) < A[k]:
#         t = max(t, k)

t = 0
value = A[0]
for k in range(1, n):
    # print("A[0:{}]={}".format(k, A[:k]))
    # print("{} <? {}".format(2 * sum(A[:k]), A[k]))
    if 2 * value < A[k]:
        t = max(t, k)
    value += A[k]


print(n - t)
### BUGGY CODE ###

import numpy as np
def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for v in [x, y]:
        p = np.argsort(v)
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = {i: i for i in range(n)}
    def find(i):
        if parent[i] == i:
            return i
        else:
            return find(parent[i])
    def union(i, j):
        i = find(i)
        j = find(j)
        if i > j:
            i, j = j, i
        parent[j] = i
    que = sorted(que, key=lambda _: _[2])
    ans = 0
    while que != []:
        u, v, d = que.pop(0)
        if find(u) != find(v):
            ans += d
        union(u, v)
    return ans

n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))

### FIXED CODE ###

import numpy as np

def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for p in map(np.argsort, [x, y]):
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = [i for i in range(n)]
    def find(i):
        if parent[i] == i:
            return i
        else:
            j = find(parent[i])
            parent[i] = j
            return j
    ans = 0
    for u, v, d in sorted(que, key=lambda _: _[2]):
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            if u > v:
                u, v = v, u
            parent[v] = u
    return ans

n = int(input())
x = np.zeros(n, dtype=int)
y = np.zeros(n, dtype=int)
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))
### BUGGY CODE ###

a, b = map(int,input().split())
count = 0
for i in range(a+1):
  for j in range(a+1):
    for k in range(a+1):
      if (i+j+k) == b:
        count += 1
      else:
        continue
print(count)

### FIXED CODE ###

a, b = map(int,input().split())
count = 0
for i in range(a+1):
  for j in range(a+1):
    k = b - i - j
    if 0 <= k <= a:
      count += 1
print(count)
### BUGGY CODE ###

import math
M = 10**9+7
X,Y = map(int,input().split())
if (X+Y)/3 != (X+Y)//3:
    print(0)
    exit()
n = (X+Y)//3
r = Y-n
if r<0 or r>n:
    print(0)
    exit()
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

res = 1
for i in range(1,n+1):
    res = res*i%M
for i in range(1,r+1):
    res = res*mod_inv(i,M)%M
for i in range(1,n-r+1):
    res = res*mod_inv(i,M)%M
print(res)

### FIXED CODE ###

import math
M = 10**9+7
X,Y = map(int,input().split())
if (X+Y)/3 != (X+Y)//3:
    print(0)
    exit()
n = (X+Y)//3
r = Y-n
if r<0 or r>n:
    print(0)
    exit()


#nCr and Mod
def nCr(n, r, mod=10**9+7):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

print(nCr(n,r,M))
### BUGGY CODE ###

from collections import deque
import copy

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(node)

Visited = [False for _ in range(n+1)]
Visited[node] = True
Visited_to = [[] for _ in range(n+1)]

Colors = [x for x in range(1, max_edges+1)]
Colors_list = [[x for x in range(1, max_edges+1)] for x in range(n+1)]
Edge_colors = [[-1 for _ in range(n+1)] for _ in range(n+1)]

# print(Colors_list)

while dq:
    # Colors_copy = copy.deepcopy(Colors)    
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    # for v in Visited_from:
    #     Colors_copy.remove(Edge_colors[node][v])

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited_to[next_node].append(node)
        Visited[next_node] = True

        use_color = Colors_list[node][0]
        Colors_list[node].remove(use_color)
        Colors_list[next_node].remove(use_color)

        Edge_colors[node][next_node] = use_color
        Edge_colors[next_node][node] = use_color

 #       del Colors_copy[0]

print(max_edges)
for ab in AB:
    print(Edge_colors[ab[0]][ab[1]])

### FIXED CODE ###

from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])
# print(AB_dict)
### BUGGY CODE ###

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


### FIXED CODE ###

S = input()
m = 2019
dp = [0]*m
dp[0] = 1

acc, d = 0,1

for s in S[::-1]:
    acc = (acc + d*int(s)) % m
    dp[acc] += 1
    d = (d*10) % m

print(str(sum([n*(n-1)//2 for n in dp])))
### BUGGY CODE ###

a = int(input())
b = [sorted(list(input())) for _ in range(a)]
b.sort()
cnt = 0
for i in range(a):
    for j in range(i + 1, a):
        if b[i][0] == b[j][0]:
            if "".join(b[i]) == "".join(b[j]):
                cnt += 1
        else:
            break
print(cnt)


### FIXED CODE ###

import collections
a = int(input())
b = ["".join(sorted(list(input()))) for _ in range(a)]
b = collections.Counter(b)
total = 0
for i in b.values():
    for j in range(1, i):
        total += j
print(total)
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<p:break
   if d[t]==I:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

from math import factorial
 
def com(n, r):
  return factorial(n) // factorial(n - r) // factorial(r)
 
n, a, b = [int(s) for s in input().split()]
 
print((2**n - com(n, a) - com(n, b) - 1) % (10**9 + 7))

### FIXED CODE ###

import functools

def get_mul_inverse(x: int, p: int) -> int:
    return iterative_square(x, p - 2, p)

def _iterative_square(x: int, n: int, p: int) -> int:
    if n <= 1:
        return x
    div, mod = divmod(n, 2)
    return (((iterative_square(x, div, p) ** 2) % p) * x ** mod) % p

def iterative_square(x: int, n: int, p: int) -> int:
    if n <= 0:
        return None

    return _iterative_square(x, n, p)

def factorial(a, b, p):
  x = 1

  x = functools.reduce(lambda x, y: (x * y) % p, range(a, b + 1), 1)
  return x

def com(n, r, p):
  fact_div_r = get_mul_inverse(factorial(1, r, p), p)

  _result = factorial(n - r + 1, n, p)
  result = (_result * fact_div_r) % p
  
  return result


n, a, b = [int(i) for i in input().split()]
p = 10**9 + 7


pow_2_n_1 = iterative_square(2, n, p) - 1

_result = pow_2_n_1 - com(n, a, p)

_result = _result - com(n, b, p)

result = _result % p
print(result)
### BUGGY CODE ###

n = int(input())
list = list(map(int, input().split()))
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if list[i] + list[j] > list[k] and list[k] + list[j] > list[i] and list[k] + list[i] > list[j]:
                ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
list = list(map(int, input().split()))
list.sort()
import bisect
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        index = bisect.bisect_left(list, list[i]+list[j])
        ans += index - j -1
print(ans)
### BUGGY CODE ###

H, N = map(int, input().split())
A = [0]*N
B = [0]*N
C = [0]*N
for i in range(N):
    A[i],B[i] = map(int, input().split())
    C[i] = A[i]/B[i]
inf=float("inf")
dp = [[inf for i in range(H+1)] for j in range(N+1)]
for i in range(N+1): dp[i][0]=0
for i in range(N):
    for j in range(H+1):
        dp[i+1][j] = min(dp[i][j],dp[i+1][max(j-A[i],0)]+B[i])
print(dp[N][H])

### FIXED CODE ###

H, N = map(int, input().split())
A = [0]*N
B = [0]*N
C = [0]*N
for i in range(N):
    A[i],B[i] = map(int, input().split())
    C[i] = A[i]/B[i]
inf=float("inf")
dp = [[inf for i in range(H+1)] for j in range(N+1)]
for i in range(N+1): dp[i][0]=0
for i in range(N):
    for j in range(H+1):
        dp[i+1][j] = min(dp[i][j],dp[i+1][max(j-A[i],0)]+B[i])
print(dp[N][H])
### BUGGY CODE ###

# ducational DP Contest B-Frog 2
    
N, K = map(int, input().split())
h = list(map(int, input().split())) + [0]*K

dp = [float('inf') for _ in range(N+K)]
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))
        
print(dp[N-1])

### FIXED CODE ###

# Educational DP Contest B-Frog 2

def frog(N, K, h):
    # initialize
    inf = float('inf')
    dp = [inf] * N
    
    minKN = min(K, N)
    for i in range(minKN):
        if i == 0:
            dp[i] = 0
        else: 
            dp[i] = abs(h[0] - h[i])
            for j in range(minKN):
                if j == i:
                    continue
                elif j < i:
                    dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))
    # DP
    for i in range(N):
        if i == 0:
            continue
        elif i < K:
            continue
        else:
            dp[i] = min([abs(h[k] - h[i]) + dp[k] for k in range(i-K, i)])
    return dp[N-1]
    
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    print(frog(N, K, h))
### BUGGY CODE ###

input()
m = []
a = list(map(int, input().split()))
for x in range(min(a), max(a)+1):
    m.append(a.count(x - 1) + a.count(x) + a.count(x + 1))
print(max(m))

### FIXED CODE ###

ans = 0
input()
a = list(map(int, input().split()))
c = [0] * (10 ** 5 + 1)
for i in a:
    c[i] += 1
for x in range(min(a), max(a)+1):
    m = c[x - 1] + c[x] + c[x + 1]
    ans = max(ans, m)
print(ans)
### BUGGY CODE ###

class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def solve(self):
        b = 0
        current = self.sadness(b)
        left = self.sadness(b-1)
        right = self.sadness(b+1)
        while True:
            # print("{}: {} {} {}".format(b, left, current, right))
            if (left >= current) and (right >= current):
                print(current)
                return
            elif left < right:
                b -= 1
            else:
                b += 1
            current = self.sadness(b)
            left = self.sadness(b-1)
            right = self.sadness(b+1)

    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()

### FIXED CODE ###

class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def solve(self):
        array = self.a_s.copy()
        for i in range(self.n):
            array[i] -= i + 1
        array.sort()
        b = array[len(array) // 2]
        print(self.sadness(b))
        
    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()
### BUGGY CODE ###

# Problem D - Coloring Edges on Tree

# 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 = [[-1, 1]] # [[既に使った色], 遷移ノード]
while len(visit_queue)>0:
    p = visit_queue.pop(0)

    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 ###

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

for i in range(M // N, 0, -1):
  if M % i == 0:
    print(i)
    exit()

### FIXED CODE ###

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

for i in range(M // N, 0, -1):
  if M % i == 0:
    print(i)
    exit()
### BUGGY CODE ###

s = input().strip()
t = input().strip()

for i in range(len(s)):
    if s[i] != t[i]:
        s = s.translate(str.maketrans({s[i]:t[i], t[i]:s[i]}))

if s == t:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input().strip()
t = input().strip()

scount = []
tcount = []

for x in [chr(i) for i in range(97,97+26)]:
    scount.append(s.count(x))
    tcount.append(t.count(x))

if sorted(scount) == sorted(tcount):
    print("Yes")
else:
    print("No")