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

N = int(input())
s = [sorted(input()) for _ in range(N)]
for i in range(N):
    s[i] = ''.join(s[i])
s.sort()
t = set(s)

def tousa(n):
    return n*(n-1)//2

ans = 0
for t_i in t:
    ans += tousa(s.count(t_i))
print(ans)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
d = defaultdict(int)
for _ in range(N):
    d[''.join(sorted(input()))] += 1

def tousa(n):
    return n*(n-1)//2

ans = 0
for i in d.values():
    ans += tousa(i)
print(ans)
### BUGGY CODE ###

S=input()
N=len(S)
if N<4:
  print(0)
  exit(0)
M=2019
X=[0]+[int(S[i])*pow(10,N-1-i)%M for i in range(N)]
import itertools
X = list(itertools.accumulate(X))
ans=0
x=[]
for l in range(N-2):
  for r in range(l+4,N+1):
    if (X[l]-X[r])%M==0:
      ans+=1
      x.append([l,r])
      break
def search(a,x,j):
  while j<len(x):
    if a[1]==x[j][0]:
      return 1+search(x[j][1],x,j+1)
    j+=1
  return 0
  
for i,a in enumerate(x):
  ans+=search(a,x,i+1)
print(ans)



### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)
S=input()
S=S[::-1]
i=1
x=0
MOD=2019
for s in S:
  x+=(int(s)*i)%MOD
  x%=MOD
  d[x]+=1
  i*=10
  i%=MOD
ans=0
for k in d.values():
  ans=ans+k*(k-1)//2
print(ans+d[0])
### BUGGY CODE ###

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

# 各数字の個数を格納
dict = {}
for a in A:
    if a in dict:
        dict[a] += 1
    else:
        dict[a] = 1

# k番目の値を除いたlistで同じ数字を引く回数を出力
memo = {}
for k in range(N):
    ans = 0
    m = A[k]
    if m in memo.keys():
        ans = memo[m]
    else:
        dict_work = dict.copy()
        dict_work[m] -= 1
        for d in dict_work.values():
            if d > 1:
                ans += (d * (d - 1)) // 2
        memo[m] = ans
    print(ans)


### FIXED CODE ###

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

# 各数字の個数を格納
dict = {}
for a in A:
    if a in dict:
        dict[a] += 1
    else:
        dict[a] = 1

# k番目の値を消さない場合の場合分けの個数
ans = 0
for d in dict.values():
    if d > 1:
        ans += (d * (d - 1)) // 2

# k番目の値を除いた場合に減る場合の数を引いて答えを出力
for k in range(N):
    w = dict[A[k]]
    # 減る数
    decrease = 0
    if w == 1:
        pass
    elif w == 2:
        decrease = -1
    elif w > 2:
        decrease = ((w - 1) * (w - 2) // 2) - (w * (w - 1) // 2 )
    print(ans + decrease)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [-1] * len(D)
    XST.sort()
    for x, s, t in XST:
        s0 = bisect_left(D, s)
        t0 = bisect_left(D, t)
        for i in range(s0, t0):
            if ans[i] == -1:
                ans[i] = x
    for y in ans:
        print(y)
    return

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [-1] * Q
    nexts = [-1] * Q
    XST.sort()
    for x, s, t in XST:
        i = bisect_left(D, s)
        end = bisect_left(D, t)
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = end
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *

mod = 10**9+7
def rec(k, ti, m):
    if k == N:
        return m == 5
    if memo[k][ti][m] != -1:
        return memo[k][ti][m]
    res = 0
    d = D[N-k-1]
    if S[k] != '?':
        res += rec(k+1, ti, (m+int(S[k])*d)%13)
    else:
        for i in range(10):
            res += rec(k+1, 0, (m+i*d)%13)
    res %= mod
    memo[k][ti][m] = res
    return res

S = input()
N = len(S)
D = [None] * N
t = 1
for i in range(N):
    D[i] = t % 13
    t = t * 10 % 13
memo = [[[-1] * 13 for j in range(2)] for i in range(N+1)]
print(rec(0, 1, 0))


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *

mod = 10**9+7
S = input()
N = len(S)
D = [None] * N
t = 1
for i in range(N):
    D[i] = t % 13
    t = t * 10 % 13
dp = [[0] * 13 for i in range(N+1)]
if S[N-1] != '?':
    dp[N-1][int(S[N-1])] = 1
else:
    for i in range(10):
        dp[N-1][i] = 1
for k in range(N-1)[::-1]:
    d = D[N-k-1]
    for m in range(13):
        if S[k] != '?':
            dp[k][m] += dp[k+1][(m-d*int(S[k]))%13]
            dp[k][m] %= mod
        else:
            for i in range(10):
                dp[k][m] += dp[k+1][(m-i*d)%13]
                dp[k][m] %= mod
print(dp[0][5])
### BUGGY CODE ###

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

for k in range(1,min(K+1,42)):
    B = [0]*N
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1,i+A[i])
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
            
    for i in range(1,N):
        B[i] += B[i-1]
    A = B
print(*A)

### FIXED CODE ###

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

for k in range(1,min(K+1,45)):
    B = [0]*N
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1,i+A[i])
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
            
    for i in range(1,N):
        B[i] += B[i-1]
    A = B
print(*A)
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    S = readline().strip()
    T = readline().strip()
    N, M = len(S), len(T)

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            elif dp[i + 1][j] > dp[i][j + 1]:
                dp[i + 1][j + 1] = dp[i + 1][j]
            else:
                dp[i + 1][j + 1] = dp[i][j + 1]

    ans = []
    i, j = N, M
    while i and j:
        if S[i - 1] == T[j - 1]:
            ans.append(S[i - 1])
            i -= 1
            j -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            i -= 1

    print(''.join(reversed(ans)))
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    S = readline().strip()
    T = readline().strip()
    N, M = len(S), len(T)

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    prev = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
                prev[i + 1][j + 1] = (i, j)
            elif dp[i + 1][j] > dp[i][j + 1]:
                dp[i + 1][j + 1] = dp[i + 1][j]
                prev[i + 1][j + 1] = (i + 1, j)
            else:
                dp[i + 1][j + 1] = dp[i][j + 1]
                prev[i + 1][j + 1] = (i, j + 1)

    ans = []
    i, j = N, M
    while i and j:
        p, q = prev[i][j]
        if i > p and j > q:
            ans.append(S[p])
        i, j = p, q

    print(''.join(reversed(ans)))
    return


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

#!/usr/bin/env python
# coding: utf-8

# In[24]:


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


# In[25]:


mylist = [x for x in a]
flag = True
num = 1
ans = 0
while flag:
    if mylist[num-1] != num:
        mylist.pop(num-1)
        ans += 1
    else:
        num += 1
    if len(mylist) == 0:
        flag = False
        print(-1)
    elif mylist == list(range(1,num)):
        flag = False
        print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[42]:


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


# In[43]:


count = 0
num = 1
for i in range(N):
    if a[i] == num:
        count += 1
        num += 1
if count == 0:
    print(-1)
else:
    print(N-count)


# In[ ]:
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

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

B = [0] * N
for i in A:
    B[i-1] += 1
B = np.array(B)

K = 1
F = [0] * N
for i in range(0,N):
    f = np.sum(np.minimum(B, N-i)) / (N - i)
    while K <= f:
        print(N - i)
        K += 1
    if K == N+1:
        break
    if i == (N - 1) and K != N+1:
        while K != N+1:
            print(0)
            K += 1

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import Counter
from itertools import accumulate

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

B = list(Counter(A).values())

C = [0] * N 
for i in B:
    C[i-1] += 1

F = list(accumulate(C))

S = [0] * N
f = [0] * N
S[0] = f[0] = sum(C) 
for i in range(2, N+1):
    S[i-1] = (S[i-2] + C[i-1] + S[0] - F[i-1] ) 
    f[i-1] = S[i-1] / i

f.sort()
n = 0     
K = 1
    
while K != N+1:
    if K <= f[n]:
        print(N-n)
        K += 1
    else:
        n += 1
    if n == N:
        for i in range(N-K+1):
            print(0)
        K = N+1
### BUGGY CODE ###

n = int(input())
D = sorted(list(map(int, input().split())))
m = int(input())
T = sorted(map(int, input().split()))
for t in T:
    if t in D:
        D = D[D.index(t)+1:]
    else:
        print('NO')
        exit()
print('YES')

### FIXED CODE ###

from collections import Counter
def main():
    n = int(input())
    D = sorted(map(int, input().split()))
    m = int(input())
    T = sorted(map(int, input().split()))
    CD = Counter(D)
    CT = Counter(T).items()
    for i, c in CT:
        if CD[i] < c:
            print('NO')
            return
    print('YES')
main()
### BUGGY CODE ###

import itertools
N = int(input())
s = "MARCH"
lst = []

for i in range(N):
  begin = input()[0] 
  if begin in list(s):
    lst.append(begin)
ans = 0
for i in list(itertools.combinations(lst,3)):
  if (len(set(i)) == 3):
    ans += 1
print(ans)

### FIXED CODE ###

import itertools
N = int(input())
s = "MARCH"
dct = {"M": 0, "A": 0, "R": 0, "C": 0, "H": 0}
for i in range(N):
  begin = input()[0] 
  if begin in dct.keys():
    dct[begin] += 1
cmb = itertools.combinations(list(dct.keys()), 3)
ans = 0
for i in list(cmb):
  n = 1
  for j in i:
    n *= dct[j]
  ans += n
print(ans)
### BUGGY CODE ###

A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

m = []

for i in range(M):
    x, y, z = map(int, input().split())
    m.append([x, y, z])

m.sort(key = lambda x: x[2], reverse=True)


for j in m:
    if a[j[0]-1] + b[j[1]-1] - j[2] >= 0 and a[j[0]-1] + b[j[1]-1] - j[2] < min(a) + min(b):
        print(a[m[0][0]-1] + b[m[0][1]-1] - m[0][2])
        exit()

print(min(a) + min(b))

### FIXED CODE ###

A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

m = []
am = min(a)
bm = min(b)

for i in range(M):
    x, y, z = map(int, input().split())

    m.append(a[x-1] + b[y-1] - z )



if am + bm > min(m):
    print(min(m))
else:
    print(am + bm)
### BUGGY CODE ###

#!/usr/bin/env python3

import itertools

N, M, Q = map(int, input().split())
lis = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
cnt = 0
X = [i for i in range(1, M+1)]
Y = X * N
lis_2 = []

for i in itertools.combinations_with_replacement(Y, r=N):
    cnt = 0
    j = list(i)
    j.sort()
    for k in lis:
        if j[k[1]-1] - j[k[0]-1] == k[2]:
            cnt += k[3]
    ans = max(ans, cnt)

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

import itertools

N, M, Q = map(int, input().split())
lis = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
cnt = 0
X = [i for i in range(1, M+1)]

for i in itertools.combinations_with_replacement(X, r=N):
    cnt = 0
    j = list(i)
    for k in lis:
        if j[k[1]-1] - j[k[0]-1] == k[2]:
            cnt += k[3]
    ans = max(ans, cnt)

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

import sys
input = sys.stdin.readline

from collections import defaultdict

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def prime_factors(d,N): #素因数 1を含まないことに注意
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            c = 0
            while tmp%i == 0:
                tmp //= i
                c += 1
            if d[i] < c:
                d[i] = c
    if tmp != 1:
        if d[tmp] == 0:
            d[tmp] = 1

Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    # d = defaultdict( int)
    # for a in A:
    #     prime_factors(d, a)
    s = 1
    for a in A:
        s = s*a//gcd(s,a)
    # for key, value in d.items():
    #     s *= pow( key, value)
    ans = 0
    for a in A:
        ans += s*pow(a,Q-2,Q)
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

from collections import defaultdict

def prime_factors(d,N): #素因数 1を含まないことに注意
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            c = 0
            while tmp%i == 0:
                tmp //= i
                c += 1
            if d[i] < c:
                d[i] = c
    if tmp != 1:
        if d[tmp] == 0:
            d[tmp] = 1

Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    d = defaultdict( int)
    for a in A:
        prime_factors(d, a)
    s = 1

    for key, value in d.items():
        s *= pow( key, value)
    ans = 0
    for a in A:
        ans += s*pow(a,Q-2,Q)
    print(ans%Q)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
l = []
for i in range(N):
    l.append(i+1)
print(sum(l)-N)

### FIXED CODE ###

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

from collections import deque

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

graph = [[] for i in range(N)]

for i in range(M):
    L,R,D = map(int,input().split())
    graph[L-1].append([R-1,D])
    graph[R-1].append([L-1,-D])

#print(graph)
x = [None for i in range(N)]

def f():
    for i in range(N):
        if x[i] == None:
            x[i] = 0
            q = deque([i])
            while len(q):
                j = q.popleft()
                for k,d in graph[j]:
                    if x[k] == None:
                        q.append(k)
                        x[k] = x[j]+d
                    elif x[k] != x[j]+d:
                        return False
                        
    return True

if f():
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from collections import deque

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

graph = [[] for i in range(N)]

for i in range(M):
    L,R,D = map(int,input().split())
    graph[L-1].append([R-1,D])
    graph[R-1].append([L-1,-D])

x = [None for i in range(N)]

def f():
    for i in range(N):
        if x[i] == None:
            x[i] = 0
            q = deque([i])
            while len(q):
                j = q.popleft()
                for k,d in graph[j]:
                    if x[k] == None:
                        q.append(k)
                        x[k] = x[j]+d
                    elif x[k] != x[j]+d:
                        return False
                        
    return True

if f():
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import numpy as np
import copy

n = int(input())
x = list(map(int, input().split()))
num = 0

from heapq import heappush
from heapq import heappop

def linked_heap_sort(lst):
    heap = []
    while lst:
        heappush(heap, lst.pop())
    while heap:
        lst.append(heappop(heap))
    return lst

y = copy.copy(x)
x = linked_heap_sort(x)

for i in range(n):
  num = x.index(y[i])
  if num >= n/2:
    print(x[int(n/2)-1])
  else:
    print(x[int(n/2)])



### FIXED CODE ###

import copy

n = int(input())
x = list(map(int, input().split()))
num = 0

y = copy.copy(x)
x.sort()
num1 = x[n//2-1]
num2 = x[n//2]

for i in y:
  if i <= num1:
    print(num2)
  else:
    print(num1)
### BUGGY CODE ###

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

C = 1
A.sort(reverse=True)
B.sort(reverse=True)

aloop = 0
bloop = 0

if len(set(A)) != len(A) or len(set(B)) != len(B):
    C = 0

else:
    for k in range(N * M, 0, -1):
        if C == 0:
            break
        if k in A and k in B:
            continue
        elif (k in A and k not in B):
            C *= len([x for x in B if x > k])
        elif (k not in A and k in B):
            C *= len([x for x in A if x > k])
        else:
            C *= (len([x for x in A if x > k]) *
                  len([x for x in B if x > k]) - (N * M - k))

        C %= (10**9+7)

print(C)

### FIXED CODE ###

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

C = 1
A.sort(reverse=True)
B.sort(reverse=True)

aloop = 0
bloop = 0

if len(set(A)) != len(A) or len(set(B)) != len(B):
    C = 0

else:
    for k in range(N * M, 0, -1):
        if aloop < N and bloop < M and k == A[aloop] and k == B[bloop]:
            aloop += 1
            bloop += 1
        elif aloop < N and k == A[aloop]:
            C *= bloop
            aloop += 1
        elif bloop < M and k == B[bloop]:
            C *= aloop
            bloop += 1
        else:
            C *= (aloop * bloop - (N * M - k))

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

import copy

n, t = map(int, input().split())
L = [int(i) for i in input().split()]
LL = copy.deepcopy(L)

minvalue = L[0]
maxvalue = max(LL)
subt = 0
count = 1
flag = 0
for i in range(n-1):
  if minvalue > L[i]:
    minvalue = L[i]
    flag = 1
  if maxvalue == L[i]:
    LL.remove(maxvalue)
    maxvalue = max(LL)
  else:
    LL.remove(L[i])
  tsubt = maxvalue - minvalue
  if tsubt > subt:
    subt = tsubt
    count = 1
  elif tsubt == subt and flag == 1:
    count += 1
  flag = 0
#  print("L[i]:{0}, min:{1}, max:{2}, subt:{3}, count:{4}".format(L[i], minvalue, maxvalue, subt, count))

print(count)

### FIXED CODE ###

import copy
 
n, t = map(int, input().split())
L = [int(i) for i in input().split()]

LL = [[0] for i in range(n)]
tmax = L[-1]
for i in range(n):
  if tmax <= L[-i-1]:
    tmax = L[-i-1]
  LL[-i-1] = tmax
 
minvalue = L[0]
maxvalue = LL[0]
subt = 0
count = 1
flag = 0
flagg = 0
j = 0
for i in range(n-1):
  if minvalue > L[i]:
    minvalue = L[i]
    flag = 1
  
  maxvalue = LL[i]
 
  #if maxvalue == L[i]:
    #LL = LL[i-j+1:]
    #maxvalue = max(LL)
    #j = i+1
 
  tsubt = maxvalue - minvalue
  if tsubt > subt:
    subt = tsubt
    count = 1
  elif tsubt == subt and flag == 1:
    count += 1
  flag = 0
  #print("L[i]:{0}, min:{1}, max:{2}, subt:{3}, count:{4}".format(L[i], minvalue, maxvalue, subt, count))
 
print(count)
### BUGGY CODE ###

from collections import Counter
N, X, Y = map(int, input().split())
X -= 1; Y -= 1
dist = []
for i in range(N):
  for j in range(i+1, N):
    dist.append(min([abs(i-j), abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(j-X)]))
    
pat = Counter(dist)

for i in range(1, N):
  print(pat[i])

### FIXED CODE ###


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

pat = [0]*(N-1)

for i in range(N):
  for j in range(i+1, N):
    d = min(abs(i-j), abs(X-i)+1+abs(j-Y))
    pat[d-1] += 1

for i in range(N-1):
  print(pat[i])
### BUGGY CODE ###

n,k = map(int,input().split())
m =1
for i in range(k//n+1)[::-1]:
    if k%i==0 and k//i>=n:
        m= i
        break
print(m)

### FIXED CODE ###

n,k = map(int,input().split())
m =1
for i in range(k//n+1)[::-1]:
    if k%i==0 and k//i>=n:
        m= i
        break
print(m)
### BUGGY CODE ###

import sys

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

if len(set_v) == 1:
    print(n//2)
    sys.exit()

pattern_v = []
pattern = []

for i in set_v:
    for j in set_v:
        if i != j:
            pattern_v.append([i,j])

for s, e in pattern_v:
    tmp = []
    for k in range(n):
        if k % 2 == 0:
            tmp.append(s)
        else:
            tmp.append(e)
    pattern.append(tmp)

ans = []

for i in range(len(pattern)):
    tmp = 0
    for j in range(n):
        if pattern[i][j] != v[j]:
            tmp += 1
    ans.append(tmp)

print(min(ans))

### FIXED CODE ###

import collections

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

if len(set(v)) == 1:
    print(n//2)

else:
    v_odd = collections.Counter(v[0::2])
    v_even = collections.Counter(v[1::2])

    v_odd = list(sorted(v_odd.items(), key = lambda x:-x[1]))
    v_even = list(sorted(v_even.items(), key = lambda x:-x[1]))

    if v_odd[0][0] == v_even[0][0]:
        if v_odd[1][1] > v_even[1][1]:
            print(n - v_odd[1][1] - v_even[0][1])
        else:
            print(n - v_odd[0][1] - v_even[1][1])
 
    else:
        print(n - v_odd[0][1] - v_even[0][1])
### BUGGY CODE ###

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

import heapq  # heapqライブラリのimport
#heapq.heapify(a)  # リストを優先度付きキューへ
#heapq.heappop(a)  # 最小値の取り出し
    #heapq.heappush(a, -2)

for unko in range(k):

    denkyu=[]
    heapq.heapify(denkyu)
    cnt=0
    ans=[0]*n
    #print("start",a)
    for i,aa in  enumerate(a):
        if cnt==0:
            ans[i]+=1
            if aa>0:
                cnt+=1
                heapq.heappush(denkyu,i+aa+1)
        else:
            while 1:
                tmp=heapq.heappop(denkyu)
                if i<tmp:
                    heapq.heappush(denkyu, tmp)
                    break
                else:
                    cnt-=1
                if cnt==0:
                    break


            
            ans[i]+=cnt+1
            
            if aa>0:
                cnt+=1
                heapq.heappush(denkyu,i+aa+1)
        #print(aa,denkyu)
    #print(unko,ans,a)

    aaa=a[::-1]
    denkyu2=[]
    heapq.heapify(denkyu2)
    cnt2=0
    ans2=[0]*n
    for i,aa in  enumerate(aaa):
        if cnt2==0:
            if aa>0:
                cnt2+=1
                heapq.heappush(denkyu2,i+aa+1)
        else:
            while 1:
                tmp=heapq.heappop(denkyu2)
                if i<tmp:
                    heapq.heappush(denkyu2, tmp)
                    break
                else:
                    cnt2-=1
                if cnt2==0:
                    break


            
            ans2[i]+=cnt2
            if aa>0:
                cnt2+=1
                heapq.heappush(denkyu2,i+aa+1)

    ans2=ans2[::-1]

    flag=0
    for i,v in enumerate(ans2):
        a[i]=v+ans[i]
        if a[i]!=n:
            flag=1

    if flag==0:
        break
    #print(unko,a)


print(" ".join(list(map(str,a))))

### FIXED CODE ###

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

for _ in range(k):
    imos=[0]*(n+1)
    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,1+i+a[i])]-=1
    
    a[0]=imos[0]
    if a[0]==n:
        flag=0
    else:
        flag=1

    for i in range(1,n):
        a[i]=a[i-1]+imos[i]
        if a[i]!=n:
            flag=1
    
    if flag==0:
        break

print(" ".join(list(map(str,a))))