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

INF = float('inf')
n, k = map(int, input().split())
h = [int(i) for i in input().split()] + [0] * k
dp = [0] + [INF] * (n - 1 + k)
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 ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [0]
for i in range(1, n):
    to = min(i, k) + 1
    dp += [min([dp[-j] + abs(h[i] - h[i - j]) for j in range(1, to)])]
print(dp[-1])
### BUGGY CODE ###

#coding:utf-8
import bisect,math
A,B,Q=map(int,raw_input().split())
s=[]
t=[]
for a in range(A):
    s.append(input())
for a in range(B):
    t.append(input())
for _ in range(Q):
    x=input()
    sl=bisect.bisect_left(s,x)-1
    sr=bisect.bisect_left(s,x)
    tl=bisect.bisect_left(t,x)-1
    tr=bisect.bisect_left(t,x)
    ans=float("inf")
    if sl!=-1 and tl!=-1:
        A=max(s[sl],t[tl])
        B=min(s[sl],t[tl])
        L=abs(x-A)+abs(A-B)
        ans=min(ans,L)
    if sl!=-1 and tr!=len(t):
        L=abs(x-s[sl])*2 + abs(t[tr]-x)        
        ans=min(ans,L)
        ans=min(ans,abs(x-s[sl])+abs(t[tr]-x)*2)
    if tl!=-1 and sr!=len(s):
        ans=min(ans,abs(x-t[tl])*2+abs(s[sr]-x))
        ans=min(ans,abs(x-t[tl])+abs(s[sr]-x)*2)
    if tr!=len(t) and sr!=len(s):
        A=min(s[sr],t[tr])
        B=max(s[sr],t[tr])
        L=abs(A-x)+abs(B-A)
        ans=min(ans,L)
    print(ans)
    
    




### FIXED CODE ###

#coding:utf-8
import bisect,sys
A,B,Q=map(int,raw_input().split())
s=[0]*A
t=[0]*B
for i in range(A):    
    s[i]=int(sys.stdin.readline())
for i in range(B):
    t[i]=int(sys.stdin.readline())
buf=[]
def f(x):
    sl=bisect.bisect_left(s,x)-1
    sr=sl+1
    tl=bisect.bisect_left(t,x)-1
    tr=tl+1
    ans=float("inf")
    if sl!=-1 and tl!=-1:
        A=max(s[sl],t[tl])
        B=min(s[sl],t[tl])
        L=abs(x-A)+abs(A-B)
        ans=min(ans,L)
    if sl!=-1 and tr!=len(t):
        L=abs(x-s[sl])*2 + abs(t[tr]-x)        
        ans=min(ans,L)
        ans=min(ans,abs(x-s[sl])+abs(t[tr]-x)*2)
    if tl!=-1 and sr!=len(s):
        ans=min(ans,abs(x-t[tl])*2+abs(s[sr]-x))
        ans=min(ans,abs(x-t[tl])+abs(s[sr]-x)*2)
    if tr!=len(t) and sr!=len(s):
        A=min(s[sr],t[tr])
        B=max(s[sr],t[tr])
        L=abs(A-x)+abs(B-A)
        ans=min(ans,L)
    return str(ans)

I=[0]*Q
for i in xrange(Q):
    I[i]=int(sys.stdin.readline())
r=map(f,I)
print("\n".join(r))
### BUGGY CODE ###

n=int(input())
list=[]
ans=0
for i in range(n):
    a=int(input())
    list.append(a)
for i in range(n):
    if list.count(list[i])%2!=0:
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
list=[]
ans=0
sa=1
sas=0
for i in range(n):
    a=int(input())
    list.append(a)
list=sorted(list)
list.append(10000000000)
for i in range(n+1):
    if i!=0:
        if list[i]==list[i-1]:
            sa+=1
        else:
            sas=sa
            sa=1
            if sas%2!=0:
                ans+=1
print(ans)
### BUGGY CODE ###

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

s = 0
while True :
  f = [ i%2 == 0 for i in nums]
  if all(f) :
    s+=1
    nums = [ i%2 for i in nums]
  else :
    break
print(s)

### FIXED CODE ###

n = input()
A= set(map(int, input().split()))

result = []
for i in A:
  r = 0
  while i %2 == 0 :
    i = i/2
    r += 1
  result.append(r)

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

while True:
  H,W = map(int,input().split())
  if (H,W) == (0,0):
    break
  i = 0
  j = 0
  while i < H:
    while j < W:
      print('#')
      if j == W:
        print("\n")
      j += 1
  i += 1


### FIXED CODE ###

while True:
  H,W = map(int, input().split())
  if H == 0 and W == 0:
    break
  for i in range(H):
    print("#"*W)
  print()
### BUGGY CODE ###

n,w = map(int,input().split())
dp = [[0]*(w+1) for _ in range(n+1)]#[[0]*(w+1)] *(n+1)
for i in range(1,n+1):
    wi,vi = [int(i) for i in input().split()]
    #DPテーブルの更新
    for j in range(w+1):
        if j >= wi : #選べるかどうか
            dp[i][j] = max(dp[i-1][j] , dp[i-1][j-wi]+vi) #選ぶ場合
        else:
            dp[i][j] = max(dp[i-1][j] , dp[i][j]) #選ばない場合
print(dp[n][w])

### FIXED CODE ###

n,w = map(int,input().split())
dp = [[0]*(w+1) for _ in range(n+1)]#[[0]*(w+1)] *(n+1)
for i in range(1,n+1):
    wi,vi = [int(i) for i in input().split()]
    #DPテーブルの更新
    for j in range(w+1):
        if j >= wi : #選べるかどうか
            dp[i][j] = max(dp[i-1][j] , dp[i-1][j-wi]+vi) #選ぶ場合
        else:
            dp[i][j] = max(dp[i-1][j] , dp[i][j]) #選ばない場合
print(dp[n][w])
### BUGGY CODE ###

x = int(input())
ans = 1
for i in range(2, 1000):
    j = 2
    while i**j <= x:
        ans = max(ans, i**j)
    j += 1
    if i > x:
        break
print(ans)


### FIXED CODE ###

x = int(input())
ans = 1
for i in range(2, 1000):
    j = 2
    while i**j <= x:
        ans = max(ans, i**j)
        j += 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
dp = {0: 1}
MOD = 10 ** 9 + 7
for i in range(n):
    compatibilities = [1 << i for i, v in enumerate(input().split()) if v == '1']
    ndp = defaultdict(lambda: 0)
    for k, p in dp.items():
        for c in compatibilities:
            if k & c:
                continue
            ndp[k | c] += p
            ndp[k | c] %= MOD
    dp = ndp
    # print(i, len(dp))
print(sum(dp.values()) % MOD)


### FIXED CODE ###

n = int(input())
dp = [0] * (1 << n)
dp[0] = 1
curr = {0}
MOD = 10 ** 9 + 7
for i in range(n):
    compatibilities = [1 << i for i, v in enumerate(input().split()) if v == '1']
    nxt = set()
    for k in curr:
        p = dp[k] % MOD
        for c in compatibilities:
            if k & c:
                continue
            dp[k | c] += p
            nxt.add(k | c)
    curr = nxt
print(dp[(1 << n) - 1] % MOD)
### BUGGY CODE ###

N = int(input())

num = 1
for i in range(N, 0, -2):
    num = num * i
    
number = str(num)

cnt = 0
for i in range(1, len(number)+1):
    if number[-i] == '0':
        cnt += 1
    else :
        break

print(cnt)

### FIXED CODE ###

N = int(input())

# N が奇数の場合は 0 になる
if N % 2 == 1:
    print(0)
else :
    n = N // 10
    cnt = n
    while n >= 5:
        n = n // 5
        cnt += n
    print(cnt)
### BUGGY CODE ###

L,R=map(int,input().split())

keep=L*R
for i in range(L,R+1):
  for j in range(i+1,R+1):
    mod=(i*j) % 2019
    if mod<keep:
      keep=mod
      j=j+2019
print(keep)

### FIXED CODE ###

L,R=map(int,input().split())

keep=2018
for i in range(L,R+1):
  for j in range(i+1,R+1):
    keep=min(keep,(i*j)%2019)
    if keep==0:
      print(0)
      exit()
print(keep)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(N-1):
    for j in range(i+1,N):
        ans=(ans+A[i]*A[j])%(10**9+7)
print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
wa=[0]*(N-1)
wa[0]=A[-1]
for i in range(1,N-1):
    wa[i]=wa[i-1]+A[N-i-1]
ans=0
wa.reverse()

for i in range(0,N-1):

    ans=(ans+wa[i]*A[i])%(10**9+7)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
def fctr(n):
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    return f

mod=10**9+7
fuc=[1]
def fucfun(n):
    for i in range(1,n):
        e=fuc[i-1]*i
        fuc.append(e%mod)
def com(n,k):
    com=(fuc[n]%mod)*pow(fuc[k],mod-2,mod)*pow(fuc[n-k],mod-2,mod)
    return com
fucfun(m)
f=fctr(m)
s=1
for i in range(len(f)):
    t=com(f[i][1]+n-1,f[i][1])
    s=(s*t)%mod
print(s)

### FIXED CODE ###

n,m=map(int,input().split())
pem=1
if m==1:
    print(1)
def fctr2(n): #それぞれの素因数の指数だけ出力
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append(c)
            c=0
    if n!=1:
        f.append(1)
    return f

mod=10**9+7
fuc=[1]
def fucfun(n):
    for i in range(1,n):
        e=fuc[i-1]*i
        fuc.append(e%mod)
def com(n,k):
    com=(fuc[n]%mod)*pow(fuc[k],mod-2,mod)*pow(fuc[n-k],mod-2,mod)
    return com
f=fctr2(m)
if m!=1:
    a=max(f)+n
    fucfun(a)
    s=1
    for i in range(len(f)):
        t=com(f[i]+n-1,f[i])
        s=(s*t)%mod
    print(s)
### BUGGY CODE ###

import numpy as np
import math
from fractions import gcd
n,m = map(int,input().split())
a = np.array(input().split(),dtype=int)
a /= 2

def t_per2(k):
    num = 0
    while k%2 == 0:
        k = k//2
        num += 1
    return num

f = False
dcm = a[0]
t_2 = t_per2(a[0])
for i in a:
    dcm = (dcm*i)//gcd(dcm,i)
    if dcm > m or not t_per2(i) == t_2:
        f = True
        break

count = 0
if not f:
    count = math.ceil(int(m/dcm)/2)

print(count)


### FIXED CODE ###

import numpy as np
import math
from fractions import gcd
n,m = map(int,input().split())
a = np.array(input().split(),dtype=int)
a /= 2

def t_per2(k):
    return format(k,'b')[::-1].find('1')

f = False
dcm = a[0]
t_2 = t_per2(a[0])
for i in a:
    dcm = (dcm*i)//gcd(dcm,i)
    if dcm > m or not t_per2(i) == t_2:
        f = True
        break

count = 0
if not f:
    count = math.ceil(int(m/dcm)/2)

print(count)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
for i in range(1, n+1):
    print(A.count(i))

### FIXED CODE ###

from collections import Counter
n = int(input())
A = Counter(list(map(int, input().split())))
for i in range(1, n+1):
    print(A[i])
### BUGGY CODE ###

def main():

    n = int(input())
    S = input() + 'eeee'

    cnt = 0
    for i in range(10):
        for j in range(10):
            for k in range(10):
                # tmp = str(i)+str(j)+str(k)
                m = 0
                while S[m] != str(i):
                    m += 1
                    if m >= n:
                        break
                m += 1
                while S[m] != str(j):
                    m += 1
                    if m >= n:
                        break
                m += 1
                while S[m] != str(k):
                    m += 1
                    if m >= n:
                        break
                if m < n:
                    cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

### FIXED CODE ###

n = int(input())
S = input()
l = len(S)

S += 'eeee'

cnt = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            # tmp = str(i)+str(j)+str(k)
            m = 0
            while S[m] != str(i):
                m += 1
                if m >= l:
                    break
            m += 1
            while S[m] != str(j):
                m += 1
                if m >= l:
                    break
            m += 1
            while S[m] != str(k):
                m += 1
                if m >= l:
                    break
            if m < l:
                cnt += 1

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

#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2 - 2*n):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(n*(n-1)//2)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(n*(n-1)//2+1):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.6:
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg:
        for i in a:
            if len(i) != 0:
                print(-1)
                quit()
    if not flg2:
        print(ans)
        quit()
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()

for i in range(q):
    l,r=map(int,input().split())
    ss=s[l-1:r]
    m=0
    for j in range(r-l+1):
        if j==r-l+1:
            pass
        elif ss[j:j+2]=="AC":
            m+=1
    print(m)


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)

for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

from collections import deque

N,K=map(int,input().split())
if N==1:print(K)
else:

  G=[[] for i in range(N+1)]
  deg=[0 for i in range(N+1)]
  mod=10**9+7

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

  deg2 = list(enumerate(deg))
  deg2 = sorted(deg2,key=lambda x:x[1])
  first = deg2[1][0]
  second = G[first][0]
  color = [1 for i in range(N+1)]
  color[first],color[second]=K,K-1

  def bfs(s):
      seen = [0 for i in range(N+1)]
      prev = [0 for i in range(N+1)]
      todo = deque([])
      now = s
      seen[now]=1
      todo.append(now)
      while 1:
        if len(todo)==0:break
        a = todo.popleft()
        if a != first: 
          acolor=K-1
        for b in G[a]:
          if seen[b] == 0:
            seen[b] = 1
            todo.append(b)
            prev[b] = a
            if b != second:
              acolor -= 1
              color[b] = acolor
      return prev

  prev = bfs(first)
  total=1
  for i in range(1,N+1):
    total *= color[i] % mod
  total %= mod
  print(total)

### FIXED CODE ###

from collections import deque

N,K=map(int,input().split())
mod = 10**9+7
G=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)

def bfs(s):
    seen = [0]*N
    prev = [0]*N
    color = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    color[s]=K
    while todo:
      a = todo.popleft()
      if a == start: count = K-1
      else: count = K-2
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          color[b] = count %mod
          count -= 1
    return color
  
MAX,start = 0,-1
for i in range(N):
  if len(G[i])>MAX:
    MAX=len(G[i])
    start = i
    
color = bfs(start)
ans = 1
for i in range(N):
  ans *= color[i]
  ans %= mod
  
print(ans)
### BUGGY CODE ###

###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N = int(input())
V = list(mi())

oddl = []
evenl = []
cnt = 0
for v in V:
  if cnt % 2 == 0: oddl.append(v)
  else: evenl.append(v)
  cnt += 1

#oddl, evenlに含まれる数の二次元リストを作り、数が多い順にソートする
ocontents = []
econtents = []
oddsetl = list(set(oddl))
evensetl = list(set(evenl))
for o in oddsetl:
  ocontents.append((o, oddl.count(o)))
for e in evensetl:
  econtents.append((e, evenl.count(e)))
ocontents = sorted(ocontents, key=lambda x:-x[1])
econtents = sorted(econtents, key=lambda x:-x[1])

Nd2 = round(N/2) #それぞれの個数
if ocontents[0][0] != econtents[0][0]:
  print(Nd2-ocontents[0][1] + Nd2-econtents[0][1])
elif ocontents[0][1] >= econtents[0][1]:
  if len(econtents)==1: print(Nd2-ocontents[0][1] + Nd2)
  else: print(Nd2-ocontents[0][1] + Nd2-econtents[1][1])
else:
  if len(ocontents)==1: print(Nd2 + Nd2-econtents[0][1])
  else: print(Nd2-ocontents[1][1] + Nd2-econtents[0][1])





### FIXED CODE ###

###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N = int(input())
V = list(mi())

oddl = V[0::2]
evenl = V[1::2]

#oddl, evenlに含まれる数をバケットソートする。個数をバケツに入れる
obuckets = [0]*(10**5 + 1)
ebuckets = [0]*(10**5 + 1)
for o in oddl:
  obuckets[o] += 1
for e in evenl:
  ebuckets[e] += 1

o1cnt = max(obuckets)
o1 = obuckets.index(o1cnt)
obuckets[o1] = 0

o2cnt = max(obuckets)
o2 = obuckets.index(o2cnt)
obuckets[o2] = 0

e1cnt = max(ebuckets)
e1 = ebuckets.index(e1cnt)
ebuckets[e1] = 0

e2cnt = max(ebuckets)
e2 = ebuckets.index(e2cnt)
ebuckets[e2] = 0

Nd2 = round(N/2) #それぞれの個数
if o1 != e1:
  print(Nd2-o1cnt + Nd2-e1cnt)
else: print(min(Nd2-o1cnt + Nd2-e2cnt, Nd2-o2cnt + Nd2-e1cnt))
### BUGGY CODE ###

n=int(input())
import math

def comb(x):
    if x<6:
        return 0
    count=0
    for i in range(1,int(math.sqrt(x-2))):
        if i**2+2*i>x-3:
            break
        for j in range(i,int(math.sqrt(x-2))):
            if i**2+j**2+(i+1)*(j+1)>x+1:
                break
#            if 3*(i**2+j**2)+2*i*j-4*x>0:
#                break
            k=(-i-j+math.sqrt((i+j)**2-4*(i**2+j**2+i*j-x)))/2
            if k<j:
                break
            elif k.is_integer() and k>0:
                if len(set([i,j,k]))==3:
                    count+=6
                elif len(set([i,j,k]))==2:
                    count+=3
                else:
                    count+=1
    
                
            """
            for k in range(j,int(math.sqrt(x-2))):
                if i**2+j**2+k**2+i*j+j*k+k*i>x:
                    break
                if i**2+j**2+k**2+i*j+j*k+k*i==x:
                    if len(set([i,j,k]))==3:
                        count+=6
                    elif len(set([i,j,k]))==2:
                        count+=3
                    else:
                        count+=1
            """
    return count

for i in range(1,n+1):
#    print(i,comb(i))
    print(comb(i))

### FIXED CODE ###

n=int(input())
a=[0]*(10**5)
for i in range(1,101):
    for j in range(1,101):
        for k in range(1,101):
            a[i**2+j**2+k**2+i*j+j*k+k*i]+=1
for i in range(n):
    print(a[i+1])
### BUGGY CODE ###

# abc084_d.py
'''
通常の素数判定（√N まで割り続ける方法）ではTLEするので
エラトステネスの篩をリストで用意しておく。
'''
def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n%2 == 0:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    return True

def is_like_num(n):
    return is_prime(n) and is_prime((n+1)//2)

erast_list = [is_like_num(i) for i in range(100001)]
# print(erast_list[:6].count(True))
# print(erast_list[:6])
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    print(erast_list[:R+1].count(True)-erast_list[:L].count(True))

### FIXED CODE ###

def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n%2 == 0:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    return True

def is_like_num(n):
    return is_prime(n) and is_prime((n+1)//2)

erast_list =[0]*100001
cnt = 0
for i in range(100001):
    if is_like_num(i):
        cnt+=1
    erast_list[i] = cnt
# print(erast_list[:5])
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
#    print(erast_list[R+1],erast_list[L-1])
    print(erast_list[R+1]-erast_list[L-1])
### BUGGY CODE ###

k, q = map(int, input().split())
d = list(map(int, input().split()))
nxm = [map(int, input().split()) for _ in range(q)]

for n, x, m in nxm:
    dd = [e % m for e in d]

    ans = n - 1
    divq, divr = divmod(n - 1, k)

    dd_r = dd[:divr]

    ans -= dd.count(0) * divq
    ans -= dd_r.count(0)

    last = x + sum(dd) * divq + sum(dd_r)
    ans -= last // m - x // m

    print(ans)


### FIXED CODE ###

import numpy as np

k, q = map(int, input().split())
d = np.array(input().split(), np.int64)
nxm = [map(int, input().split()) for _ in range(q)]

for n, x, m in nxm:
    dd = d % m

    ans = n - 1
    divq, divr = divmod(n - 1, k)

    dd_r = dd[:divr]

    ans -= (k - np.count_nonzero(dd)) * divq
    ans -= divr - np.count_nonzero(dd_r)

    last = x + np.sum(dd) * divq + np.sum(dd_r)
    ans -= last // m - x // m

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

from operator import itemgetter

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

A_list  = []


for _ in range(N):
    A, B = map(int, input().split())
    A_list.append([A, B])

A_list.sort(key=itemgetter(0))


dp = [0]*(M+1)

for i in range(1, M+1):

    for j in range(len(A_list)):
        if A_list[j][1]>0:
            A_list[j][1]-=1
            break
    
    dp[i] = dp[i-1]+A_list[j][0]

print(dp[M])

### FIXED CODE ###

import sys

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

L = []
for _ in range(N):
    A,B = map(int, input().split())
    L.append([A,B])

L = sorted(L, key=lambda x: x[0])

sum = 0
for i in range(len(L)):
    l = L[i]
    if l[1]<M:
        M = M - l[1]
        sum = sum + l[0]*l[1]
    else:
        sum = sum + l[0]*M
        print(sum)
        sys.exit()      

print(sum)
### BUGGY CODE ###

n = int(input())
a = list(map(str,input().split()))
b = []

for i in a:
    b.append(i)
    b.reverse()

print(' '.join(b))

### FIXED CODE ###

from collections import deque
n = int(input())
a = list(map(str,input().split()))
d = deque()

for i in range(len(a)):
    if i%2==0:
        d.append(a[i])
    else:
        d.appendleft(a[i])

if n%2==1:
    d.reverse()

print(' '.join(d))
### BUGGY CODE ###



def read_input():
    n = int(input())
    alist = list(map(int, input().split()))
    return n, alist


def submit():
    n, alist = read_input()


    count = {}
    for a in alist:
        if a not in count.keys():
            count[a] = 1
        else:
            count[a] += 1

    count = list(count.items())
    pruned = []
    for c in count:
        if c[1] > 1:
            if c[1] % 2 == 0:
                pruned.append((c[0], 2))
            else:
                pruned.append((c[0], 1))
        else:
            pruned.append(c)

    f = False
    for c in pruned:
        if c[1] == 2:
            f = not f

    if f:
        print(len(pruned) - 1)
    else:
        print(len(pruned))

    return


if __name__ == '__main__':
    submit()


### FIXED CODE ###



def read_input():
    n = int(input())
    alist = list(map(int, input().split()))
    return n, alist


def submit():
    n, alist = read_input()

    count = {}
    count_t = 0
    for a in alist:
        if a not in count.keys():
            count[a] = False
        else:
            count[a] = not count[a]
            if count[a]:
                count_t += 1
            else:
                count_t -= 1

    if count_t % 2 == 0:
        print(len(count))
    else:
        print(len(count) - 1)




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

n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
cnt = 0
        
while len(arr):
  i = arr[0]
  tmp = []
  original = True
  for j in arr[1:]:
    if i == j:
      original = False
    if j % i != 0:
      tmp += [j]
  if original:
    cnt += 1
  arr = tmp
    

print(cnt)

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
li = [0]*(m+1)
cnt = 0
        
for i in arr:
  for j in range(i, m+1, i):
    li[j] += 1

for i in arr:
  if li[i] == 1:
    cnt += 1

print(cnt)