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

n = int(input())
a = list(map(int, input().split()))
 
x = 0
for i in range(n-1):
  while True:
    if a[i] > a[i + 1]:
      a[i + 1] += 1
      x += 1
    if a[i] <= a[i + 1]:
      break
 
print(x)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
ans = 0
for i in range(N-1):
    if A[i]>A[i+1]:
        ans += A[i]-A[i+1]
        A[i+1] = A[i]
print(ans)
### BUGGY CODE ###

from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()#queueに入っていたものを消す。
        if [y, x] == [gy, gx]:#もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          l = 1
          while p == 0:
              new_y, new_x = y + j * l, x + k * l #改行して条件文を続けるときにバックスラッシュ
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                elif visited[new_y][new_x] == -1:#まだ来たことない点だったという条件
                  visited[new_y][new_x] = visited[y][x] + 1
                  queue.append([new_y, new_x])#新しい点を足す。
              else:
                p = 1
              l += 1
              if l == K + 1:
                p = 1

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
C = [0] * H
for i in range(H):
  C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
#print(visited)
print(visited[x2][y2])
  




### FIXED CODE ###

from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()#queueに入っていたものを消す。
        if [y, x] == [gy, gx]:#もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          l = 1
          while p == 0:
              new_y, new_x = y + j * l, x + k * l 
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                elif visited[new_y][new_x] == -1:#まだ来たことない点だったという条件
                  visited[new_y][new_x] = visited[y][x] + 1
                  queue.append([new_y, new_x])#新しい点を足す。
                elif visited[new_y][new_x] < visited[y][x] + 1:
                  p = 1
              else:
                p = 1
              l += 1
              if l == K + 1:
                p = 1

H, W, K = map(int, input().split())
#K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
C = [0] * H
for i in range(H):
  C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
#print(visited)
print(visited[x2][y2])
### BUGGY CODE ###

#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        a = X10
        if (a>>(i-1) & 1) and X10_num1 >1:
            a -= 2**(i-1)
            amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)

        elif (a>>(i-1) & 1) and X10_num1 ==1:
            print(0)
            continue
        else:
            a += 2**(i-1)
            amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)

        print(1+f(amari))


main()


### FIXED CODE ###

#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        j = N-i
        if (X[j] == '1') and X10_num1 >1:
            mod = X10_num1-1
            amari = (X10_ninus - pow(2,i-1,mod))%(mod) 
        elif (X[j] == '1') and X10_num1 ==1:
            print(0)
            continue
        else:
            mod = X10_num1+1
            amari = (X10_pulse + pow(2,i-1,mod))%(mod)

        print(1+f(amari))


main()
### BUGGY CODE ###

import sys
n=int(input())
r=list(map(int,sys.stdin.read().split()))
print(max([max(r[i+1:])-r[i]for i in range(n-1)]))

### FIXED CODE ###

import sys
def f():
 s=1e10;b=-s
 input()
 for r in map(int,sys.stdin):
  if b<r-s:b=r-s
  if s>r:s=r
 print(b)
f()
### BUGGY CODE ###

# https://atcoder.jp/contests/abc094/tasks/arc095_b
n = int(input())
nums = [int(i) for i in input().split()]

# すべてを計算する時間はなさそう
# 最大のモノを選らんで、それと絶対値差が大きいモノを選ぶ。いや、ここは全部やればいいのかな。
mod = (10 ** 9 + 7) ** 2
MAX = 2 * (10 ** 6) + 1 # これは変動するので注意。せいぜい10 ** 6くらいまでがTLEの限界

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n, r):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

t = -float('inf')
MAX = max(nums)
ans = None
for num in nums:
    if num == MAX:
        continue
    r = nCr(MAX, num)
    if r > t:
        t = r
        ans = (MAX, num)
print(*ans)

### FIXED CODE ###

# https://atcoder.jp/contests/abc094/tasks/arc095_b
n = int(input())
nums = [int(i) for i in input().split()]

# すべてを計算する時間はなさそう
# 最大のモノを選らんで、それと絶対値差が大きいモノを選ぶ。いや、ここは全部やればいいのかな。
# numsの値がめちゃくちゃでかいので、全部はできない。

MAX = max(nums)
t = 0
ans = 0
for num in nums:
    if num == MAX:
        continue
    d = min(MAX - num, num)
    if t < d:
        t = d
        ans = num
print(MAX, ans)
### BUGGY CODE ###

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

num_list = [i for i in range(a, b+1, 1)]
copy = num_list.copy()
copy.sort(reverse=True)
ans_list = []
for j in num_list:
    if num_list.index(j) <= k-1 or copy.index(j) <= k-1:
        ans_list.append(j)

for k in ans_list:
    print(k)

### FIXED CODE ###

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

num_limit = b-a+1
if num_limit <= k*2:
    ans_list = [i for i in range(a, b+1, 1)]
else:
    ans_list = []
    for j in range(k):
        low = a+j
        high = b-j
        ans_list.append(low)
        ans_list.append(high)
    ans_list.sort()

for l in ans_list:
    print(l)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
ptn = 0
for i in range(n+1):
    if i*r > n:
        break
    
    for j in range(n+1):
        if i*r + j*g > n:
            break
        
        if ((n - i*r - j*g)%b) == 0:
            ptn += 1
        
print(ptn)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
b,g,r = sorted([r,g,b])

ptn = 0
for i in range(n+1):
    if i*r > n:
        break
    
    for j in range(n+1):
        if i*r + j*g > n:
            break
        
        if ((n - i*r - j*g)%b) == 0:
            ptn += 1
        
print(ptn)
### BUGGY CODE ###

s1=input()
s2=input()
a=[[0]*(len(s2)+1) for i in range(len(s1)+1)]
res=''
for i in range(1,len(s1)+1):
  for j in range(1,len(s2)+1):
    if s1[i-1] == s2[j-1]:
      a[i][j] = a[i-1][j-1] + 1
    elif a[i-1][j] >= a[i][j-1]:
      a[i][j] = a[i-1][j]
    else:
      a[i][j] = a[i][j-1]
i=len(s1)
j=len(s2)
while i>0 and j>0:
  if a[i][j] == a[i-1][j]:
    i -= 1
  elif a[i][j] == a[i][j-1]:
    j -= 1
  else:
    res = s1[i-1] + res
    i -= 1
    j -= 1   
print(res)

### FIXED CODE ###

s1=input()
s2=input()
a=[[0]*(len(s2)+1) for i in range(len(s1)+1)]
res=''
for i in range(1,len(s1)+1):
  for j in range(1,len(s2)+1):
    if s1[i-1] == s2[j-1]:
      a[i][j] = a[i-1][j-1] + 1
    elif a[i-1][j] >= a[i][j-1]:
      a[i][j] = a[i-1][j]
    else:
      a[i][j] = a[i][j-1]
i=len(s1)
j=len(s2)
while i>0 and j>0:
  if a[i][j] == a[i-1][j]:
    i -= 1
  elif a[i][j] == a[i][j-1]:
    j -= 1
  else:
    res = s1[i-1] + res
    i -= 1
    j -= 1   
print(res)
### BUGGY CODE ###

import numpy as np
import math as m

def main(**kwargs):
    mod = 10 ** 9 + 7
    r = repeatSquare(2, n, mod) - 1
    r -= m.factorial(n) * repeatSquare(m.factorial(n - a) * m.factorial(a), mod - 2, mod)
    r -= m.factorial(n) * repeatSquare(m.factorial(n - b) * m.factorial(b), mod - 2, mod)
    r = r % mod
    return r

def repeatSquare(n, p, m):
    if p == 0:
        return 1

    if p % 2 == 0:
        tmp = repeatSquare(n, p/2, m)
        return tmp * tmp % m

    return n * repeatSquare(n, p-1, m)

if __name__ == "__main__":
    cin = np.array(input().split(" ")).astype("int")
    n, a, b = cin

    cout = main(n=n, a=a, b=b)
    print(cout)

### FIXED CODE ###

import numpy as np
import math as m

def main(**kwargs):
    mod = 10 ** 9 + 7
    r = repeatSquare(2, n, mod) - 1
    r -= factMod(n, n - a + 1, mod) * repeatSquare(factMod(a, 1, mod), mod - 2, mod)
    r -= factMod(n, n - b + 1, mod) * repeatSquare(factMod(b, 1, mod), mod - 2, mod)
    r %= mod
    return r

def repeatSquare(n, p, m):
    if p == 0:
        return 1

    if p % 2 == 0:
        tmp = repeatSquare(n, p/2, m) % m
        return tmp * tmp % m

    return n * repeatSquare(n, p-1, m) % m

def factMod(n, r, m):
    res = n

    while n > r:
        n -= 1
        res *= n
        res %= m

    return res

if __name__ == "__main__":
    
    cin = np.array(input().split(" ")).astype("int")
    n, a, b = cin

    cout = main(n=n, a=a, b=b)
    print(cout)
### BUGGY CODE ###

X,Y,A,B,C = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))
p = sorted(p)
q = sorted(q)
r = sorted(r)
P = A - X
Q = B - Y
R = C - 1
found = True
while R >= 0:
    if P < A:
        if (r[R] >= p[P]):
            if (q[Q] >= p[P]):
                P += 1
                R -= 1
        elif Q < B:
            if (r[R] > q[Q]):
                Q += 1
                R -= 1
            else:
                break
    elif Q < B:
        if (r[R] > q[Q]):
                Q += 1
                R -= 1
        else:
            break    
    else:
        break
print(sum(p[P:])+sum(q[Q:])+sum(r[R+1:]))

### FIXED CODE ###

X,Y,A,B,C = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))
p = sorted(p)
q = sorted(q)
r = sorted(r)
P = A - X
Q = B - Y
R = C - 1
found = True
for i in range(C+1):
    if R < 0:
        break
    if P < A:
        if (r[C-i-1] >= p[P]):
            if Q < B:
                if (q[Q] >= p[P]):
                    P += 1
                    R -= 1
                elif r[C-i-1] > q[Q]:
                    Q += 1
                    R -= 1
                else:
                    break
            else:
                P += 1
                R -= 1
        elif Q < B:
            if r[C-i-1] > q[Q]:
                Q += 1
                R -= 1
            else:
                break
        else:
            break
    elif Q < B:
        if r[C-i-1] > q[Q]:
            Q += 1
            R -= 1
        else:
            break    
    else:
        break
print(sum(p[P:])+sum(q[Q:])+sum(r[R+1:]))
### BUGGY CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
for n in range(N):
    ndp = [1]
    for m in range(M):
        if S[n] == T[m]:
            ndp.append(ndp[-1] + dp[m+1])
            dpleft[m] = dp[m+1]
        else:
            ndp.append(ndp[-1] + dpleft[m])
    dp = ndp
print(dp[-1] % MOD)

### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = ndp[m] + dp[m+1]
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
    dp = ndp[:]
print(dp[-1] % MOD)
### BUGGY CODE ###

from collections import deque
INF = int(1e9) + 7
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))



def bfs(x, y):
    d = [[INF] * w for i in range(h)]
    dx = [1,0]
    dy = [0,1]
    if s[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0
    que = deque([(0, 0)])

    while len(que) != 0:
        val = que.popleft()

        for i in range(2):
            nx = val[0] + dx[i]
            ny = (val[1] + dy[i])
            if nx < h and ny < w:

                que.append((nx, ny))
                if (s[nx][ny] == '#') and (d[nx][ny] > d[val[0]][val[1]]):
                    d[nx][ny] = min(d[val[0]][val[1]] + 1, d[nx][ny])
                elif s[nx][ny] != '#' and d[nx][ny] < d[val[0]][val[1]]:
                    d[nx][ny] = d[nx][ny]

                else:
                    d[nx][ny] = d[val[0]][val[1]]
    return d[h-1][w-1]
print(bfs(h, w))

### FIXED CODE ###

INF = int(1e9) + 7
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))

dp = [[INF] * w for i in range(h)]
if s[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0
#print(dp)

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        val1 = dp[i-1][j]
        if s[i][j] == '#' and s[i-1][j] == '.':
            val1 += 1
        val2 = dp[i][j-1]
        if s[i][j] == '#' and s[i][j-1] == '.':
            val2 += 1
        dp[i][j] = min(val1, val2)
        #print(i, j,val1, val2)
print(dp[h-1][w-1])
#print(dp)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*n for i in range(k+1)]

for i in range(n):
    dp[0][i]=a[i]
    
for ki in range(1,k+1):
    for ni in range(n):
        for j in range(ni-dp[ki-1][ni],ni+dp[ki-1][ni]+1):
            if j>=0 and j<n:
                dp[ki][j]+=1
           
for i in range(n):
    print(dp[k][i],end=" ")
print()


### FIXED CODE ###

n,k=map(int,input().split())
dp2=list(map(int,input().split()))
    
k=min(k,41)
for ki in range(1,k+1):
    ims=[0]*(n+1)
    for ni in range(n):
        if 0>ni-dp2[ni]:
            ims[0]+=1
        else:
            ims[ni-dp2[ni]]+=1
        if n<ni+dp2[ni]+1:
            ims[n]-=1
        else:
            ims[ni+dp2[ni]+1]-=1

    dp2[0]=ims[0]
    for ni in range(1,n):
        dp2[ni]=dp2[ni-1]+ims[ni]
    
for i in range(n):
    print(dp2[i],end=" ")
print()
### BUGGY CODE ###

from collections import Counter
s=input()
l=[]
l.insert(0,0)
for i in range(1,len(s)+1):
    l.append(int(s[-i:])%2019)
c=Counter(l)
ans=0
for v in c.values():
    ans += v*(v-1)//2
print(ans)

### FIXED CODE ###

from collections import Counter
S=list(map(int,input()))
P=2019
N=len(S)
if P not in [2,5]:
  pt = [1]
  for i in range(N):
    pt.append(pt[-1]*10%P)
  dp = [(S[0]*pt[N-1])%P]
  for i in range(1,N):
    dp.append((dp[-1]+S[i]*pt[N-1-i])%P)

  c = Counter(dp)
  ans = sum(u*(u-1)//2 for u in c.values())
  print(ans+c[0])
elif P==2:
  S = [int(c) for c in input()]
  ans = 0
  for i in range(N):
    if S[i]%2==0:
      ans += i+1
  print(ans)
else:
  ans = 0
  S = [int(c) for c in input()]
  for i in range(N):
    if S[i]%5==0:
      ans += i+1
  print(ans)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
from queue import PriorityQueue
from fractions import gcd
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
#  def gcd(*numbers):
#      return functools.reduce(math.gcd, numbers)
#  def make_divisors(n):
#      divisors = []
#      for i in range(1, int(n**0.5)+1):
#          if n % i == 0:
#              divisors.append(i)
#              if i != n // i:
#                  divisors.append(n//i)

#      divisors.sort(reverse=True)
#      return divisors

K = _I()

ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            ans += math.gcd(math.gcd(a,b),c)
print(ans)
exit()


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
from queue import PriorityQueue
from fractions import gcd
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def gcd(*numbers):
    return functools.reduce(math.gcd, numbers)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

K = _I()

ans = 0
d = {}
vals = []
for i in range(1, K+1):
    for j in range(1, K+1):
        nums = [i,j]
        nums.sort()
        key = str(i) + '-' + str(j)
        if key in d:
            vals.append(d[key])
        else:
            val = gcd(i,j)
            d[key] = val
            vals.append(val)
#  print(vals)
#  print(d)
for val in vals:
    for k in range(1, K+1):
        #  print(val, k)
        nums = [i,j]
        nums.sort()
        key = str(val) + '-' + str(k)
        if key in d:
            ans += d[key]
        else:
            val = gcd(val, k)
            ans += val
            d[key] = val
print(ans)
exit()
### BUGGY CODE ###

from itertools import combinations
from math import log10
s = input()
tmp = []
num = [0]
for char in s:
    tmp.append(char)
    num.append(int("".join(tmp)))

c = 0
for m, n in combinations(num, 2):
    if m == 0:
        check = n
    else:
        check = n - m * 10 ** (-int(-log10(n)) - -int(-log10(m)))
    if check % 2019 == 0:
        c += 1

print(c)


### FIXED CODE ###

from itertools import combinations
s = input()
d = {0: 1}
tmp = 0
i = 0
for char in s[::-1]:
    tmp += int(char) * pow(10, i, 2019)
    tmp %= 2019
    if tmp not in d:
        d[tmp] = 1
    else:
        d[tmp] += 1
    i += 1

result = 0
for num, v in d.items():
    result += v * (v - 1) // 2

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


#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

import numpy as np

def main():
    N = int(input())
    As = [tuple(map(int, input().split())) for _ in range(N-1)]

    m = np.array([[0 for _ in range(N)] for _ in range(N)], dtype=int)
    for a, b in As:
        m[a-1][b-1] = 1
        m[b-1][a-1] = 1

    ans = np.array([[0 for _ in range(N)] for _ in range(N)], dtype=int)

    from collections import deque

    max_c = 1
    l = deque([(0,0)])
    while (len(l)):
        v0, c0 = l.popleft()
        c1 = 1
        for v1 in range(N):
            if m[v0][v1]:
                m[v0][v1] = 0
                m[v1][v0] = 0
                if c1 == c0:
                    c1 += 1
                max_c = max(max_c, c1)
                ans[v0][v1] = c1
                ans[v1][v0] = c1
                l.append((v1, c1))
                c1 += 1

    print(max_c)
    for u, v in As:
        print(ans[u-1][v-1])



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)


### FIXED CODE ###


#%%
import sys
sys.setrecursionlimit(100000)

def input():
    return sys.stdin.readline().rstrip()

def main():
    N = int(input())

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

    ans = [[None] for _ in range(N-1)]

    def dfs(v0, c0):
        c = 1
        for v1, e in g[v0]:
            if c==c0:
                c += 1
            ans[e] = c
            if v1 < N-1:
                dfs(v1, c)
            c += 1

    dfs(0, 0)

    print(max(ans))
    for c in ans:
        print(c)



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)
### BUGGY 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"))

### FIXED CODE ###

n,m=map(int,input().split())
s=input()
l=[0]
x,y=0,0
for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":x+=1
    l.append(x)
l.append(x)
for i in range(m):
    a,b=map(int,input().split())
    print(l[b-1]-l[a-1])
### BUGGY CODE ###

import collections
n = int(input())
vlist = list(map(int,input().split()))
even = vlist[0:n:2]
odd = vlist[1:n:2]
e_counter= collections.Counter(even)
o_counter = collections.Counter(odd)
e_v = list(e_counter.values())
e_k = list(e_counter.keys())
o_v = list(o_counter.values())
o_k = list(o_counter.keys())
ans = 10**9
#ans = len(even)-e + len(odd)-o
#print(e_k,o_k)

for i in range(len(e_v)):
  for j in range(len(o_v)):
    if e_k[i] != o_k[j]:
      ans = min(ans,len(even)-e_v[i]+len(odd)-o_v[j])
    else:
      ans = min(ans,len(even)-e_v[i]+len(odd),len(even)-o_v[i]+len(odd))
print(ans)


### FIXED CODE ###

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

v_even = v[::2]
v_odd = v[1::2]
#print(v_even,v_odd)

from collections import Counter

c_even = Counter(v_even)
c_odd = Counter(v_odd)
elist = c_even.most_common()
olist = c_odd.most_common()

if elist[0][0] != olist[0][0]:
    print(len(v) - elist[0][1] - olist[0][1])
elif len(elist) >= 2 and len(olist) >= 2:
    print(len(v) - max(elist[0][1] + olist[1][1],elist[1][1] + olist[0][1]))
elif len(elist) >= 2:
    print(len(v) - max(elist[1][1] + olist[0][1], elist[0][1]))
elif len(olist) >= 2:
    print(len(v) - max(olist[1][1] + elist[0][1], olist[0][1]))
else:
    print(n//2)
### BUGGY CODE ###

n = int(input())
x = int(input(),2)

def popcount(n):
    return bin(n).count("1")

x_pop = popcount(x)
for i in reversed(range(0,n)):
    try:
        if x&(1<<i):
            tmp_pop = x_pop - 1
        else:
            tmp_pop = x_pop + 1
        tmp = (x^(1<<i)) % tmp_pop
        if tmp <= 0:
            print(1)
            continue
        cnt = 2
        tmp = tmp % popcount(tmp)
        while tmp > 0:
            cnt += 1
            tmp %= popcount(tmp)
        print(cnt)
    except:
        print(0)

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
pcx = s.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)
### BUGGY CODE ###

import numpy as np

N = int(input())
a = list(map(int, input().split()))
ans = list(np.zeros(N, dtype = int))
ans2 = []
for i in range(N):
    p = N - 1 - i
    if a[p] != sum(ans[p::p + 1]) % 2:
        ans[p] = 1
        ans2.append(str(p + 1))
print(sum(ans))
print(" ".join(ans2))



### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = [0 for i in range(N)]
ans2 = []
for i in range(N):
    p = N - 1 - i
    if a[p] != sum(ans[p::p + 1]) % 2:
        ans[p] = 1
        ans2.append(str(p + 1))
print(sum(ans))
print(" ".join(ans2))