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

n = int(input())

G = [1]
while True:
	g = G[-1] * 2 + 1
	if g > n:
		break
	G.append(g)
G.reverse()

A = [int(input()) for _ in range(n)]
cnt = 0
for g in G:
	for j, v in enumerate(A[g:]):
		while j >= 0 and A[j] > v:
			A[j+g] = A[j]
			j = j - g
			cnt += 1
		A[j+g] = v

print(len(G))
print(*G)
print(cnt)
for a in A:
	print(a)


### FIXED CODE ###

import sys

n = int(input())
if n == 1:
	G = [1]
else:
	G = [g for g in [1, 4, 10, 23, 57, 132, 301, 701] if g < n]
	while True:
		g = int(2.25 * G[-1])
		if g > n:
			break
		G.append(g)
	G.reverse()

A = list(map(int, sys.stdin))
cnt = 0
for g in G:
	for j, v in enumerate(A[g:]):
		while j >= 0 and A[j] > v:
			A[j+g] = A[j]
			j -= g
			cnt += 1
		A[j+g] = v

print(len(G))
print(*G)
print(cnt)
for a in A:
	print(a)
### BUGGY CODE ###

import statistics
N = int(input())
X = list(map(int, input().split()))

for i in range(N):
    l = X[:i] + X[i+1:]
    print(statistics.median(l))

### FIXED CODE ###

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

l = Y[N//2-1]
r= Y[N//2]

for i in X:
    if i <= l:
        print(r)
    else:
        print(l)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,W= map(int,input().split())
ans=[0 for e in range(W+1)] 
for i in range(N):
 w,v=map(int,input().split())
 for j in range(w,W+1)[::-1]:
  ans[j]=max(ans[j-w]+v,ans[j])
print(max(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
N,W= map(int,input().split())
ans= [[float('inf') for e in range(10**5+1)] for f in range(N+1)]
for i in range(N):
 w,v=map(int,input().split())
 for j in range(0,v):
  ans[i+1][j]=min(ans[i][j],w)
 for j in range(v,10**5+1):
  ans[i+1][j]=min(ans[i][j],ans[i][j-v]+w)
print(bisect.bisect(ans[N],W))
### BUGGY CODE ###

n = int(input())
s = input()
r = []
g = []
b = []
res = 0
for i in range(n):
  if s[i] == 'R':
    r.append(i)
  elif s[i] == 'G':
    g.append(i)
  else:
    b.append(i)
if max(len(r),len(g),len(b)) == len(b):
  for i in g:
    for j in r:
      res += len(b) - int((i + j) / 2 in b) - int(2 * i - j in b) - int(2 * j - i in b)
else:
  for i in b:
    for j in r:
      res += len(g) - int((i + j) / 2 in g) - int(2 * i - j in g) - int(2 * j - i in g)
print(res)


### FIXED CODE ###

n=int(input())
s=input()
R=[]
G={}
B=[]
for i in range(n):
  if s[i]=='R':
    R.append(i+1)
  elif s[i]=='G':
    G[i+1]=G.get(i+1,0)+1
  else:
    B.append(i+1)
res=len(R)*len(G)*len(B)
for i in R:
  for j in B:
    if ((i+j)%2==0 and G.get((i+j)//2,0)==1):
      res-=1
    if G.get(2*max(i,j)-min(i,j),0)==1:
      res-=1
    if G.get(2*min(i,j)-max(i,j),0)==1:
      res-=1
print(res)
### BUGGY CODE ###

# import bisect
# # import heapq
# # from copy import deepcopy
# # from collections import deque
# # from collections import Counter
# # from itertools import accumulate
# # from itertools import permutations
# import numpy as np
# # import math
# a,b,c = map(int, input().split())
n = int(input())
# p = list(map(int, input().split()))
lis = []

def dfs(s, var):
    if len(s) == n and s not in lis:
        lis.append(s)
    else:
        for i in range(var):
            dfs(s+chr(ord('a')+i), var)

        dfs(s+chr(ord('a')+var), var+1)


dfs('a', 1)

for i in range(len(lis)):
    print(lis[i])

### FIXED CODE ###

# import bisect
# # import heapq
# # from copy import deepcopy
# # from collections import deque
# # from collections import Counter
# # from itertools import accumulate
# # from itertools import permutations
# import numpy as np
# # import math
# a,b,c = map(int, input().split())
n = int(input())
# p = list(map(int, input().split()))


def dfs(s, var):
    if len(s) == n:
        print(s)
    else:
        for i in range(var):
            dfs(s+chr(ord('a')+i), var)

        dfs(s+chr(ord('a')+var), var+1)

dfs('a',1)
### BUGGY CODE ###

# R*r + G*g + B*b == N の数
R, G, B, N = map(int, input().split())
# R, G, B = list(sorted([R, G, B]))
ans = 0
for r in range(N+1):
    for g in range(N + 1):
        if (N - (r * R + g * G)) % B != 0:
            continue
        b = (N - (r * R + g * G))/B
        if b < 0:
            continue
        if r * R + g * G + b * B == N:
            ans += 1
print(ans)


### FIXED CODE ###

# R*r + G*g + B*b == N の数
R, G, B, N = map(int, input().split())
R, G, B = list(sorted([R, G, B], reverse=True))
ans = 0
for r in range(N + 1):
    for g in range(N + 1):
        if (N - (r * R + g * G)) % B != 0:
            continue
        b = (N - (r * R + g * G))/B
        if b < 0:
            break
        if r * R + g * G + b * B == N:
            ans += 1
        elif r * R + g * G + b * B > N:
            break

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

import numpy as np

def draft(A, K, N):
    K = min(K, 20)
    for _ in range(1, K+1):# 2 * 10**5
        tmp = np.zeros(N, dtype=np.int64)
        for i in range(N):# 2 * 10**5
            L = i - A[i]
            R = i + A[i] + 1
            if L < 0:
                tmp[0] += 1
            else:
                tmp[L] += 1
            if R < N:
                tmp[R] -= 1
        A = np.cumsum(tmp)
    for i in range(N):
        print(int(A[i]), end=" ")

def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)
    draft(A, K, N)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def draft(A, K, N):
    for _ in range(1, K+1):# 2 * 10**5
        tmp = [0]*(N+1)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        f = True
        for i in range(N):
            tmp[i+1] += tmp[i]
            A[i] = tmp[i]
            if A[i] != N:
                f = False
        if f:
            break
    for i in range(N):
        print(A[i], end=" ")

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

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

import numpy as np
import collections
n = int(input())
A = np.array(list(map(int,input().split())))
B = np.array([i+1 for i in range(n)])
C,D = A+B,B-A
x = max(max(C),1)
ans = 0

c = collections.Counter(C)
d = collections.Counter(D)
ans = 0
for i in range(x):
    ans += c[i]*d[i]
print(ans)


### FIXED CODE ###

import numpy as np
import collections
n = int(input())
A = np.array(list(map(int,input().split())))
B = np.array([i+1 for i in range(n)])
C,D = A+B,B-A
ans = 0

c = collections.Counter(C)
d = collections.Counter(D)
ans = 0
for i in c.keys():
    ans += c[i]*d[i]
print(ans)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush

def dijkstra(start,node,edge):
    d = [2*10**5] * node
    m = [0]*node
    d[start] = 0
    q = [0]
    heapify(q)
    
    while(len(q) != 0):
      i = heappop(q)
      di = d[i]
      for j in edge[i]:
        if(d[j] > di+1):
          d[j] = di + 1
          heappush(q, j)
          m[j] = i+1
    return m

def main():
    N,M = map(int, input().split())
    
    E = [[] for _ in [0]*N]
    for i in range(M):
      a,b = (int(x) for x in input().split())
      E[a-1].append(b-1)
      E[b-1].append(a-1)

    m = dijkstra(0, N, E)
    print("Yes")
    print("\n".join(map(str, m[1:])))

if __name__ == '__main__':
    main()


### FIXED CODE ###

from heapq import heapify, heappop, heappush

def dijkstra(start,node,edge):
    d = [2*10**5] * node
    m = [0]*node
    d[start] = 0
    q = [(0,0)]
    heapify(q)
    
    while(len(q) != 0):
      ci, i = heappop(q)
      di = d[i]
      for j in edge[i]:
        if(d[j] > di+1):
          d[j] = di + 1
          heappush(q, (di+1,j))
          m[j] = i+1
    return m

def main():
    N,M = map(int, input().split())
    
    E = [[] for _ in [0]*N]
    for i in range(M):
      a,b = (int(x) for x in input().split())
      E[a-1].append(b-1)
      E[b-1].append(a-1)

    m = dijkstra(0, N, E)
    print("Yes")
    print("\n".join(map(str, m[1:])))

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

from copy import copy, deepcopy
from collections import Counter
from math import sqrt, floor, factorial
from itertools import permutations, combinations, combinations_with_replacement
from operator import mul
from functools import reduce
import bisect

MOD = 10**9 + 7
INF = float('inf')

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

#A = [0 for i in range(N)]
B = [0 for i in range(N)]

# print(A)
for _ in range(K):
    for i in range(N):
        B[i] = 0
    for i in range(N):
        tmp = A[i]
        B[max(i-tmp, 0)] += 1
        idx = min(i+tmp+1, N)
        if idx != N:
            B[idx] -= 1
    # print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    # print(B)
    for i in range(N):
        A[i] = B[i]
    if sum(A) == N**2:
        break

L = " ".join([str(x) for x in A])
print(L)


### FIXED CODE ###

from copy import copy, deepcopy
from collections import Counter
from math import sqrt, floor, factorial, log
from itertools import permutations, combinations, combinations_with_replacement
from operator import mul
from functools import reduce
import bisect

MOD = 10**9 + 7
INF = float('inf')

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

#A = [0 for i in range(N)]
B = [0 for i in range(N)]

# print(A)
for _ in range(K):
    B = [0 for i in range(N)]
    for i in range(N):
        B[max(i-A[i], 0)] += 1
        idx = min(i+A[i]+1, N)
        if idx != N:
            B[idx] -= 1
    # print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    # print(B)
    A = B.copy()
    if _ > 10 * int(log(N)):
        break

L = " ".join([str(x) for x in A])
print(L)
### BUGGY CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)

INF = 1 << 60

# ここから書き始める
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [INF] * n
dp[0] = 0
for i in range(1, n):
    for j in range(max(0, i - k), i):
        dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]))
print(dp[-1])


### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)

INF = 1 << 60

# ここから書き始める
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [INF] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j == n:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
print(dp[-1])
### BUGGY CODE ###

# coding: utf-8
# Your code here!

N,K,Q=map(int,input().split())
A=[input() for i in range(Q)]

for i in range(N):
    if K-Q+int(A.count(str(i+1)))>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
 
P = [0] * N
for i in range(Q):
    tmp = int(input()) - 1
    P[tmp] += 1
 
sumP = sum(P)
for n in range(N):
    ans = 'No'
    total = sumP - P[n]
    if  K - total > 0:
        ans = 'Yes'
    print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input=sys.stdin.readline


#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    H,W=map(int,input().split())
    maze=[list(input()) for i in range(H)]
    pos=deque([])

    D= [[True]*(W+2)]                                  #True True True True
    D+=[[True]+[False]*W+[True] for i in range(H)]     #True FalseFalseTrue
    D.append([True]*(W+2))                             #True True True True

    for i in range(H) :
        for j in range(W) :
            if maze[i][j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :                             #forではなく各if構文だと通った…
        h,w,depth=pos.popleft()
        if not D[h+1][w] :
            pos.append([h+1,w,depth+1])
            D[h+1][w]=True

        if not D[h-1][w] :
            pos.append([h-1,w,depth+1])
            D[h-1][w]=True

        if not D[h][w+1] :
            pos.append([h,w+1,depth+1])
            D[h][w+1]=True

        if not D[h][w-1] :
            pos.append([h,w-1,depth+1])
            D[h][w-1]=True

    return depth            

print(search())



### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline


#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    H,W=map(int,input().split())
    pos=deque([])

    D= [[True]*(W+2)]                                  #True True True True
    D+=[[True]+[False]*W+[True] for i in range(H)]     #True FalseFalseTrue
    D.append([True]*(W+2))                             #True True True True

    for i in range(H) :
        maze=input()
        for j in range(W) :
            if maze[j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :
        h,w,depth=pos.popleft()
        if not D[h+1][w] :
            pos.append([h+1,w,depth+1])
            D[h+1][w]=True

        if not D[h-1][w] :
            pos.append([h-1,w,depth+1])
            D[h-1][w]=True

        if not D[h][w+1] :
            pos.append([h,w+1,depth+1])
            D[h][w+1]=True

        if not D[h][w-1] :
            pos.append([h,w-1,depth+1])
            D[h][w-1]=True

    return depth            

print(search())
### BUGGY CODE ###

import heapq

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

hq = []
for l in L:
    heapq.heappush(hq, l*(-1))

result = 0
while hq:
    a = heapq.heappop(hq)

    hq1 = []
    while hq:
        b = heapq.heappop(hq)

        hq2 = []
        while hq:
            c = heapq.heappop(hq)
            hq2.append(c)

            if a > b + c:
                result += 1

            else:
                break

        hq1.append(b)
        for v in hq2:
            heapq.heappush(hq, v)

    for v in hq1:
        heapq.heappush(hq, v)

print(result)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(lambda l: int(l)*(-1), input().split()))
L.sort()

result = 0
for i, a in enumerate(L[:-2:]):
    for ii, b in enumerate(L[i+1:-1:]):
        c_list = L[i+ii+2::]
        c_index = bisect_left(c_list, a-b)
        result += c_index

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

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

def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

out = 0
p = 998244353
for i in range(K+1):
    out += M*comb(N-1,i,p)*power_func(M-1,N-1-i,p)
    out = out % p
print(out)

### FIXED CODE ###

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

MAXN = 2*(10**5)+10
p = 998244353
MOD = p
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

out = 0
for i in range(K+1):
    out += M*nCr(N-1,i,p)*power_func(M-1,N-1-i,p)
    out = out % p
print(out)
### BUGGY CODE ###

def solve():
    from heapq import heappush, heappop, merge
    from collections import defaultdict

    N, Q = map(int, input().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    i = 0
    for _ in range(Q):
        d = int(input())
        while i < 2*N and events[i][0] <= d:
            if events[i][1] > 0:
                heappush(constructions, events[i][2])
                under_construction[events[i][2]] = True
            else:
                under_construction[events[i][2]] = False
            i += 1
        while constructions:
            x = heappop(constructions)
            if under_construction[x]: # x is the minimum coordinate under construction
                heappush(constructions, x)
                print(x)
                break
        else: # no constructions
            print(-1)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

n, k = list(map(int, input().split()))
b = list(map(int, input().split()))
a = [0 for i in range(n)]
m = set(b)
ans = 0
for l in range(n):
    a[b[l]-1] += 1
c = [item for item in a if item != 0]
for j in range(len(m)-k):
    ans += min(c)
    c.pop(c.index(min(c)))
print(ans)


### FIXED CODE ###

n, k = list(map(int, input().split()))
b = list(map(int, input().split()))
a = [0 for i in range(n)]
m = set(b)
ans = 0
for l in range(n):
    a[b[l]-1] += 1
c = [item for item in a if item != 0]
c.sort(reverse=True)
balls = sum(c[0:k])
print(n-balls)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    a.sort()
    a[n-1]=a[n-1]//2

ans=0
for i in range(n):
    ans+=a[i]
print(ans)


### FIXED CODE ###

import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
lis=[]
for i in range(n):
    heapq.heappush(lis,-a[i])
for i in range(m):
    b=(heapq.heappop(lis)*(-1)//2)*(-1)
    heapq.heappush(lis,b)
    #print(lis)
ans=0
#print(lis)
for i in range(n):
    ans+=lis[i]
print(-ans)
### BUGGY CODE ###

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

INF = 1 << 40

# dp初期化
dp = [INF] * n
dp[0] = 0

for i in range(1, n):
    dp[i] = min(dp[j] + abs(arr[i] - arr[j]) for j in range(max(i - k, 0), i))

print(dp[n - 1])

### FIXED CODE ###

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

# dp初期化
dp = [float("inf")] * n
dp[0] = 0

for i in range(1, n):
    dp[i] = min(dp[j] + abs(arr[i] - arr[j]) for j in range(max(i - k, 0), i))

print(dp[n - 1])
### BUGGY CODE ###

import itertools
N=int(input())
gu=list(map(int,input().split()))
ans=[]
for v in itertools.permutations(gu):
    cnt=2
    k=(v[0]+v[1])/2
    while cnt<=N-1:
        k=(k+v[cnt])/2
        cnt+=1
    ans.append(k)
print(max(ans))        
        

### FIXED CODE ###

N=int(input())
gu=list(map(int,input().split()))
gu.sort()
ans=[]
cnt=2
k=(gu[0]+gu[1])/2
while cnt<=N-1:
        k=(k+gu[cnt])/2
        cnt+=1
    
print(k)
### BUGGY CODE ###

all_num, select_num = map(int, input().split())
dice = [int(a) for a in input().split()]
max_sum = 0

for i in range(all_num - (select_num - 1)):
    this_sum = sum(dice[i:(i + select_num)])
 
    if this_sum > max_sum:
        max_sum = this_sum

print((max_sum + select_num) * 0.5)

### FIXED CODE ###

all_num, select_num = map(int, input().split())
dice = [int(a) for a in input().split()]

for i in range(all_num - (select_num - 1)):
    if i == 0:
        max_sum = this_sum = sum(dice[i:(i + select_num)])
    else:
        this_sum = this_sum - dice[i - 1] + dice[i + select_num - 1]

        if this_sum > max_sum:
            max_sum = this_sum

print((max_sum + select_num) * 0.5)
### BUGGY CODE ###

def f(i):
    return sum(range(1, i + 1)) / i


n, k = [int(i) for i in input().split()]
p = [f(int(i)) for i in input().split()]
ans = sum(p[0:k])
for i in range(1, n - 2):
    ans = max(ans, sum(p[i : i + k]))
print(ans)


### FIXED CODE ###

def f(x):
    return (x + 1) / 2


n, k = [int(i) for i in input().split()]
p = [f(int(i)) for i in input().split()]
ans = sum(p[:k])
a = ans
for i in range(k, n):
    a = a + p[i] - p[i - k]
    ans = max(ans, a)
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from fractions import gcd

n = int(readline())
a = list(map(int, readline().split()))
ans = 0
gcd_ans = a[0]
lcm_ans = a[0]
mod = 10 ** 9 + 7
for i in range(1, n):
    gcd_ans = gcd(lcm_ans, a[i])
    lcm_ans = lcm_ans * a[i] // gcd_ans
for i in range(n):
    ans += lcm_ans // a[i]
    ans %= mod
print(ans % mod)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
A = list(map(int, readline().split()))
mod = 10 ** 9 + 7


def lcm(X, Y):
    x = X
    y = Y
    if y > x:
        x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return X * Y // y


cnt = 0
ans = 0
LCM = 1
for i in range(n):
    Q = lcm(LCM, A[i])
    cnt *= Q // LCM
    LCM = Q
    cnt += Q // A[i]
print(cnt % mod)
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    N = int(input())
    A_list = [int(input()) for _ in range(N)]

    num_cnt_list = [0 for _ in range(10**9+1)]

    for i in A_list:
        num_cnt_list[i] += 1
    
    res_list = [i%2 for i in num_cnt_list]

    print(sum(res_list))


if __name__ == "__main__":
    resolve()


### FIXED CODE ###


def resolve():
    '''
    code here
    '''
    import collections

    N = int(input())
    A_list = [int(input()) for _ in range(N)]
    cnt_dic = collections.Counter(A_list)

    cnt = 0
    for v in cnt_dic.values():
        if v % 2 == 1:
            cnt += 1

    print(cnt)

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

N,Q=map(int,input().split())
S=input()
count = [1 if S[i:i+2] =='AC' else 0 for i in range(0,N-1)]
for i in range(0,Q):
  l,r=map(int,input().split())
  print(sum(count[l-1:r-1]))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
t=[0]*N
for i in range(0,N-1):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(0,Q):
  l,r=map(int,input().split())
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

from itertools import accumulate

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

for j in range(k):
    a01 = [0] * (n + 1)
    for i, ai in enumerate(a):
        l, r = max(0, i - ai), min(i + ai + 1, n)
        a01[l] += 1
        a01[r] -= 1
    a = list(accumulate(a01))
    if a == [n] * n:
        break
print(*a[:-1])


### FIXED CODE ###

from itertools import accumulate
from math import log2

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

for j in range(k):
    a01 = [0] * (n + 1)
    for i, ai in enumerate(a):
        l, r = max(0, i - ai), min(i + ai + 1, n)
        a01[l] += 1
        a01[r] -= 1
    a = list(accumulate(a01))
    if all(ai == n for ai in a[:-1]):
        break
print(*a[:-1])