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

dic = {}

def comb(n,k,p):
  from math import factorial
  
  if n / 2 < k:
    k = n - k
  
  if n<0 or k<0 or n<k: 
    return 0
  if n==0 or k==0: 
    return 1
  
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
  if (a,b) in dic:
    return dic[(a,b)]
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    dic[(a,b)] = d*d %p
    return d*d %p
  if b%2==1:
    dic[(a,b)] = (a*power_func(a,b-1,p))%p
    return (a*power_func(a,b-1,p))%p

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


count = 0
i = n - 1
j = k - 1
k = 0
while True:
  tmp = comb(i, j, 10**9+7)
  count += tmp * a[-1-k]
  count -= tmp * a[k]
  count = count % (10 ** 9 + 7)
  if i == j:
    break
  i -= 1
  k += 1
    
print(count)

### FIXED CODE ###

# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def main():
  MOD = 10 ** 9 + 7
  n,k = map(int,input().split())
  a = sorted(list(map(int,input().split())))
  
  g_k = 1
  for i in range(1,k):
    g_k *= i
    g_k %= MOD
    
  gyakugen = pow_k(g_k,MOD-2,MOD)
  array = [0] * (n+1)
  array[k-1] = g_k
  
  for i in range(k, n+1):
    array[i] = array[i-1] * i * pow_k(i-k+1,MOD-2,MOD)
    array[i] %= MOD
    
  ans = 0
  for i in range(n):
    if i-k+1 >= 0:        
      ans += array[i] * gyakugen * a[i]
      
    if n-i-k >= 0:
      ans -= array[n-i-1] * gyakugen * a[i]
      
    ans %= MOD
      
  print(ans)

main()
### BUGGY CODE ###

N = int(input())
names = []
words = {}
for i in range(N):
    name = input()
    if name not in names:
        words[name] = 1
        names.append(name)
    elif name in names:
        words[name] += 1

max_num = max(words.values())
max_name_list = [word[0] for word in words.items() if word[1] == max_num]

max_name_list = sorted(max_name_list)

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


### FIXED CODE ###

from collections import Counter
N = int(input())

counter = Counter()
for i in range(N):
    s = input()
    counter[s] += 1


lst = list(counter.most_common())
max_num = lst[0][1]

for l in sorted(lst):
    if l[1] == max_num:
        print(l[0])
### BUGGY CODE ###

import bisect
n,q=map(int,input().split())

event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append([s-x,1,x])
    event.append([t-x,-1,x])
event.sort()
d=[int(input()) for _ in range(q)]

k=0
stop=[]
for i in range(q):
    while k<2*n and event[k][0]<=d[i]:
        if event[k][1]==1: bisect.insort(stop,event[k][2])
        else: stop.remove(event[k][2])
        k+=1
    print(stop[0] if stop!=[] else -1)

### FIXED CODE ###

def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)

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

    event=[]
    for _ in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,1,x))
        event.append((t-x,-1,x))

    for i in range(q):
        event.append((int(input()),2,i))
    event.sort()

    ans=[0]*q

    stop=set()
    hq=[]
    for t,op,x in event:
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)

        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

main()
### BUGGY CODE ###

#JMD
#Nagendra Jha-4096

 
import sys
import math

#import fractions
#import numpy
 
###File Operations###
fileoperation=0
if(fileoperation):
    orig_stdout = sys.stdout
    orig_stdin = sys.stdin
    inputfile = open('W:/Competitive Programming/input.txt', 'r')
    outputfile = open('W:/Competitive Programming/output.txt', 'w')
    sys.stdin = inputfile
    sys.stdout = outputfile

###Defines...###
mod=1000000007
 
###FUF's...###
def nospace(l):
    ans=''.join(str(i) for i in l)
    return ans
 
 
 
##### Main ####
t=1
for tt in range(t):
    n=int(input())
    #n,k,s= map(int, sys.stdin.readline().split(' '))
    a=list(map(int,sys.stdin.readline().split(' ')))
    ams=1
    for x in a:
        ams*=x

    if ams>pow(10,18):
        ams=-1

    print(ams)
    
    
#####File Operations#####
if(fileoperation):
    sys.stdout = orig_stdout
    sys.stdin = orig_stdin
    inputfile.close()
    outputfile.close()

### FIXED CODE ###

#JMD
#Nagendra Jha-4096

 
import sys
import math

#import fractions
#import numpy
 
###File Operations###
fileoperation=0
if(fileoperation):
    orig_stdout = sys.stdout
    orig_stdin = sys.stdin
    inputfile = open('W:/Competitive Programming/input.txt', 'r')
    outputfile = open('W:/Competitive Programming/output.txt', 'w')
    sys.stdin = inputfile
    sys.stdout = outputfile

###Defines...###
mod=1000000007
 
###FUF's...###
def nospace(l):
    ans=''.join(str(i) for i in l)
    return ans
 
 
 
##### Main ####
t=1
for tt in range(t):
    n=int(input())
    #n,k,s= map(int, sys.stdin.readline().split(' '))
    a=list(map(int,sys.stdin.readline().split(' ')))
    ams=1

    if 0 in a:
        print(0)
        continue
        
    for x in a:
        ams*=x
        if ams> 1000000000000000000:
            ams=-1
            break

    print(ams)
    
    
#####File Operations#####
if(fileoperation):
    sys.stdout = orig_stdout
    sys.stdin = orig_stdin
    inputfile.close()
    outputfile.close()
### BUGGY CODE ###

mod = 10**9+7
s = input()
n = len(s)
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(10):
        if s[i] != "?" and int(s[i]) != j: continue
        for k in range(13):
            dp[i+1][(k*10+j)%13] += dp[i][k]
    for j in range(13):
        dp[i+1][j] %= mod
        
# for i in range(n+1): print(dp[i])
print(dp[n][5])

### FIXED CODE ###

mod = 10**9+7
s = input()
n = len(s)
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(10):
        if s[i] != "?" and int(s[i]) != j: continue
        for k in range(13):
            dp[i+1][(k*10+j)%13] += dp[i][k]
    for j in range(13):
        dp[i+1][j] %= mod
        
# for i in range(n+1): print(dp[i])
print(dp[n][5])
### BUGGY CODE ###

from collections import deque

H, W = [int(_) for _ in input().split()]
C = [int(_) - 1 for _ in input().split()]
D = [int(_) - 1 for _ in input().split()]

S = [input() for _ in range(H)]
V = [[-1 for w in range(W)] for h in range(H)]

V[C[0]][C[1]] = 0

pool = deque()
pool.append(tuple([0, C[0], C[1]]))
while(pool):
    c, y, x = pool.pop()
    if c != V[y][x]:
        continue
    for dx in [-2, -1, 0, 1, 2]:
        for dy in [-2, -1, 0, 1, 2]:
            if y + dy < 0 or H <= y + dy:
                continue
            if x + dx < 0 or W <= x + dx:
                continue
            if S[y+dy][x+dx] == "#":
                continue
            if (dx, dy) in [(-1,0),(1,0),(0,-1),(0,1)]:
                if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x]:
                    V[y+dy][x+dx] = V[y][x]
                    pool.appendleft((c, y+dy, x+dx))
            elif V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x] + 1:
                V[y+dy][x+dx] = V[y][x] + 1
                pool.append((c+1, y+dy, x+dx))
print(V[D[0]][D[1]])


### FIXED CODE ###

from collections import deque

H, W = [int(_) for _ in input().split()]
C = [int(_) - 1 for _ in input().split()]
D = [int(_) - 1 for _ in input().split()]

S = [input() for _ in range(H)]
V = [[-1 for w in range(W)] for h in range(H)]

V[C[0]][C[1]] = 0

pool = deque()
pool.append(tuple([0, C[0], C[1]]))
while(pool):
    c, y, x = pool.popleft()
    if c != V[y][x]:
        continue
    for dx in [-2, -1, 0, 1, 2]:
        for dy in [-2, -1, 0, 1, 2]:
            if y + dy < 0 or H <= y + dy:
                continue
            if x + dx < 0 or W <= x + dx:
                continue
            if S[y+dy][x+dx] == "#":
                continue
            if (dx, dy) in [(-1,0),(1,0),(0,-1),(0,1)]:
                if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x]:
                    V[y+dy][x+dx] = V[y][x]
                    pool.appendleft((c, y+dy, x+dx))
            elif V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x] + 1:
                V[y+dy][x+dx] = V[y][x] + 1
                pool.append((c+1, y+dy, x+dx))
print(V[D[0]][D[1]])
### BUGGY CODE ###

#!/usr/bin/env python3

n = int(input())
d = [int(x) for x in input().split()]
m = int(input())
t = [int(x) for x in input().split()]
for et in t:
    if et not in d:
        print("NO")
        exit()
    d.remove(et)
print("YES")


### FIXED CODE ###

#!/usr/bin/env python3

import collections
n = int(input())
d = collections.Counter([int(x) for x in input().split()])
m = int(input())
t = collections.Counter([int(x) for x in input().split()])
for k, v in t.items():
    if d[k] < v:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

N = int(input())
li = list(map(int,input().split()))
ans = []
for i in range(N):
  ans.append(li.index(i+1) + 1)
for i in range(N):
  print(ans[i],end=' ')

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
li = list(map(int,input().split()))
ans = [0] * N
for i in range(N):
    ans[li[i]-1] = i+1
for j in range(N):
    print(ans[j],end = ' ')
### BUGGY CODE ###

n, k = map(int, input().split())
a = [int(x) for x in input().split()]

ans = sum(a[0:k])
for i in range(1, n-k+1):
    nxt = sum(a[i:i+k])
    if ans < nxt:
        print('Yes')
    else:
        print('No')
    ans = nxt


### FIXED CODE ###

n, k = map(int, input().split())
a = [int(x) for x in input().split()]

ans = sum(a[0:k])
for i in range(1, n-k+1):
    nxt = ans - a[i-1] + a[i+k-1]
    if ans < nxt:
        print('Yes')
    else:
        print('No')
    ans = nxt
### BUGGY CODE ###

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

from math import hypot,acos,atan2,cos,sin
def circles_cross_points(x1,y1,r1,x2,y2,r2):
    d = hypot(x1-x2, y1-y2)
    if r1 + r2 < d or abs(r1 - r2) >= d: return []
    x = (r1**2 + d**2 - r2**2) / (2*r1*d)
    if not -1 <= x <= 1: return []
    a = acos(x)
    t = atan2(y2-y1, x2-x1)
    return [
        (x1+cos(t+a)*r1, y1+sin(t+a)*r1),
        (x1+cos(t-a)*r1, y1+sin(t-a)*r1)
    ]

eps = 10e-10
def is_ok(t):
    cands = []
    for x,y,_ in XYC:
        cands.append((x,y))
    for i,(x1,y1,c1) in enumerate(XYC[:-1]):
        for x2,y2,c2 in XYC[i+1:]:
            ps = circles_cross_points(x1,y1,t/c1,x2,y2,t/c2)
            cands += ps
    for cx,cy in cands:
        k = 0
        for x,y,c in XYC:
            d = hypot(cx-x,cy-y)
            if c*d <= t + eps:
                k += 1
                if k >= K:
                    return True
    return False

ok = 10**10
ng = 0
for _ in range(100):
    m = (ok+ng)/2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

### FIXED CODE ###

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

from math import hypot,acos,atan2,cos,sin
def circles_cross_points(x1,y1,r1,x2,y2,r2):
    d = hypot(x1-x2, y1-y2)
    if r1 + r2 < d or abs(r1 - r2) >= d: return []
    x = (r1**2 + d**2 - r2**2) / (2*r1*d)
    if not -1 <= x <= 1: return []
    a = acos(x)
    t = atan2(y2-y1, x2-x1)
    return [
        (x1+cos(t+a)*r1, y1+sin(t+a)*r1),
        (x1+cos(t-a)*r1, y1+sin(t-a)*r1)
    ]

eps = 10e-10
def is_ok(t):
    cands = []
    for x,y,_ in XYC:
        cands.append((x,y))
    for i,(x1,y1,c1) in enumerate(XYC[:-1]):
        for x2,y2,c2 in XYC[i+1:]:
            ps = circles_cross_points(x1,y1,t/c1,x2,y2,t/c2)
            cands += ps
    for cx,cy in cands:
        k = 0
        for x,y,c in XYC:
            d = hypot(cx-x,cy-y)
            if c*d <= t + eps:
                k += 1
                if k >= K:
                    return True
    return False

ok = 10**10
ng = 0
for _ in range(100):
    m = (ok+ng)/2
    if is_ok(m):
        ok = m
    else:
        ng = m
    if ok-ng < 10e-7: break
print(ok)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a,b,k = map(int,input().split())

for i in range(k):
    if a >= 1:
        a -= 1
    elif b >= 1:
        b -= 1
print(a,b)


### FIXED CODE ###

# -*- coding: utf-8 -*-
a,b,k = map(int,input().split())
"""
for i in range(k):
    if a >= 1:
        a -= 1
    elif b >= 1:
        b -= 1
print(a,b)
"""

if k <= a and a >= 1:
    a = a - k
elif k <= a + b and b >= 1:
    c = a
    a = 0
    b = b - (k - c)
else:
    a = 0
    b = 0
print(a, b)
### BUGGY CODE ###

import copy
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
for i in range(n):
    tmp = copy.copy(a)
    tmp[i] = 0
    print(max(tmp))

### FIXED CODE ###

import copy
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
tmp = copy.copy(a)
tmp.sort()
max_num = tmp[-1]
min_num = tmp[-2]
for i in range(n):
    if a[i] == max_num:
        print(min_num)
    else:
        print(max_num)
### BUGGY CODE ###



def popcount(n):
  if n == 0:
    return 0

  cnt = 0
  for bit in format(n, 'b'):
    if bit == '1':
      cnt += 1

  return 1 + popcount(n % cnt)

def main():
  n = int(input())
  src = input()
  base = int(src, 2)

  for i in range(n - 1, -1, -1):
    num = base + 2 ** i if src[n - i - 1] == '0' else base - 2 ** i
    print(popcount(num))



main()


### FIXED CODE ###


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

  return cnt

def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1) if base_cnt > 1 else 0

  for i, s in enumerate(src):
    i = n - 1 - i
    num = None

    if s == '0':
      mod = base_cnt + 1
      num = (basep + pow(2, i, mod)) % mod
    elif base_cnt > 1:
      mod = base_cnt - 1
      num = (basem - pow(2, i, mod)) % mod
    else:
      print(0)
      continue

    print(1 + f(num))


main()
### BUGGY CODE ###

MOD = 10**9 + 7

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


k = int(input())
s = input()
n = len(s)
ans = 0

fact, inv = prepare(10**6, MOD)
for i in range(k+1):
    c25 = 1
    for j in range(i):
        c25 *= 25
        c25 % MOD
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD
    c26 = 1
    for h in range(k-i):
        c26 *= 26
        c26 % MOD
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)

### FIXED CODE ###

MOD = 10**9 + 7

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


k = int(input())
s = input()
n = len(s)
ans = 0

l = k+n + 3
 
a25 = [1]
for i in range(l):
    a25.append((a25[-1] * 25) % MOD)
a26 = [1]
for i in range(l):
    a26.append((a26[-1] * 26) % MOD)

fact, inv = prepare(n+k, MOD)
for i in range(k+1):
    c25 = a25[i]
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD

    c26 = a26[k-i]
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

import sys


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


def main():
    N, K, Q = map(int, input().split())
    points = [K] * N

    for _ in range(Q):
        a = int(input()) - 1
        for i in range(N):
            if i != a:
                points[i] -= 1

    for p in points:
        if p > 0:
            print('Yes')
        else:
            print('No')


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


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


def main():
    N, K, Q = map(int, input().split())
    win = [0] * N

    for _ in range(Q):
        a = int(input()) - 1
        win[a] += 1

    for w in win:
        is_win = K - (Q - w) > 0
        if is_win:
            print('Yes')
        else:
            print('No')


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

import itertools
n = int(input())
s = input()
ans = set()
for x in itertools.combinations(s,3):
    ans.add(x)
print(len(ans))

### FIXED CODE ###

int(input())
s = list(input())
ans = 0
for i in range(10):
    if str(i) in s:
        ss = s[s.index(str(i))+1:]
        for j in range(10):
            if str(j) in ss:
                sss = ss[ss.index(str(j))+1:]
                for k in range(10):
                    if str(k) in sss:
                        ans += 1
print(ans)
### BUGGY CODE ###

import sys
from copy import deepcopy
from functools import lru_cache
sys.setrecursionlimit(10**6)

def main():
    #node i is list of [child,size,comb] connected i
    #return [size,comb]
    @lru_cache(maxsize=1000000)
    def deep(i,parent):
        if len(node[i])==1 and parent!=-1:
            return [1,1]
        mysize=0
        mycomb=1
        for j in node[i]:
            if j!=parent:
                size,comb=deep(j,i)
                mysize+=size
                mycomb=(mycomb*comb)%mod
                mycomb=(mycomb*inv[size])%mod
        mycomb=(mycomb*fact[mysize])%mod
        return (mysize+1,mycomb)

    F = 2*10**5
    mod = 10**9+7
    fact = [1]*F
    inv = [1]*F
    for i in range(2,F):
        fact[i]=(fact[i-1]*i)%mod
    inv[F-1]=pow(fact[F-1],mod-2,mod)
    for i in range(F-2,1,-1):
        inv[i] = (inv[i+1]*(i+1))%mod
    
    n=int(input())
    node=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        node[a-1].append(b-1)
        node[b-1].append(a-1)
    for i in range(n):
        print(deep(i,-1)[1])

main()

### FIXED CODE ###

n=int(input())
F = n+5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

#invnum[0] cant be used
invnum=[fact[i-1]*inv[i] for i in range(n)]

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

stack=[0]
order=[0]
parent=[-1]*n
comb=[0]*n
size=[1]*n

# BFS order
while stack:
    node = stack.pop()
    for neib in graph[node]:
        if neib!=parent[node]:
            stack.append(neib)
            order.append(neib)
            parent[neib]=node

#calc size including self
for node in order[n-1:0:-1]:
    size[parent[node]]+=size[node]

#calc root comb
comb[0]=fact[n-1]
for node in range(1,n):
    comb[0]*=invnum[size[node]]
    comb[0]%=mod

#calc all comb
for node in order[1:]:
    comb[node]=comb[parent[node]]*size[node]*invnum[n-size[node]]%mod

print(*comb,sep="\n")
### BUGGY CODE ###

n, m = map(int, input().split())
friends = [0 for i in range(n)]
relation = [[False for i in range(n)] for j in range(n)]

for i in range(m):
  a, b = map(int, input().split())
  if not relation[a - 1][b - 1]:
    relation[a - 1][b - 1] = True
    relation[b - 1][a - 1] = True
    friends[a - 1] += 1
    friends[b - 1] += 1

print(max(friends) + 1)

### FIXED CODE ###

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
n, m = map(int, input().split())
par = [-1]*n

for i in range(m):
  a, b = map(int, input().split())
  unite(a - 1, b - 1)

ans = 0
for i in range(n):
  ans = max(ans, size(i))

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

import copy

N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))

B = copy.deepcopy(A)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if j == k:
                continue
            if k == i:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            if A[i][j] == A[i][k] + A[k][j]:
                B[i][j] = 0

ans = 0
for i in range(N):
    for j in range(i, N):
        ans += B[i][j]

print(ans)



### FIXED CODE ###

import copy

N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))

B = copy.deepcopy(A)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if j == k:
                continue
            if k == i:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            if A[i][j] == A[i][k] + A[k][j]:
                B[i][j] = 0

ans = 0
for i in range(N):
    for j in range(i, N):
        ans += B[i][j]

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

import sys
from operator import itemgetter
from collections import deque, Counter
from itertools import permutations, combinations
from heapq import heapify, heappop, heappush
from bisect import bisect, bisect_left

def search(n, x, m, K, D):
    ini = x % m
    modD = [D[i] % m for i in range(K)]
    roop , rem = (n - 1) // K, (n - 1) % K
    last = ini
    equal = 0
    for i in range(K):
        if i < rem and rem > 0:
            if modD[i] == 0: equal += roop + 1
            else: last += (roop + 1) * modD[i]
        else:
            if modD[i] == 0: equal += roop
            else: last += roop * modD[i]
    up = (last // m) - (ini // m)
    return n - 1 - equal - up

def solve():
    input = sys.stdin.readline
    K, Q = map(int, input().split())
    D = [int(d) for d in input().split()]
    Ans = []
    for _ in range(Q):
        n, x, m = map(int, input().split())
        Ans.append(search(n, x, m, K, D))

    for i, a in enumerate(Ans): print(a)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from operator import itemgetter
from collections import deque, Counter
from itertools import permutations, combinations
from heapq import heapify, heappop, heappush
from bisect import bisect, bisect_left

def search(n, x, m, K, D):
    ini = x % m
    modD = [D[i] % m for i in range(K)]
    roop , rem = (n - 1) // K, (n - 1) % K
    last = ini
    equal = 0
    for i in range(K):
        if i < rem and rem > 0:
            if modD[i] == 0: equal += roop + 1
            else: last += (roop + 1) * modD[i]
        else:
            if modD[i] == 0: equal += roop
            else: last += roop * modD[i]
    up = (last // m) - (ini // m)
    return n - 1 - equal - up

def solve():
    input = sys.stdin.readline
    K, Q = map(int, input().split())
    D = [int(d) for d in input().split()]
    Ans = []
    for _ in range(Q):
        n, x, m = map(int, input().split())
        Ans.append(search(n, x, m, K, D))

    for i, a in enumerate(Ans): print(a)

    return 0

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

N= int(raw_input())
a = map(int, raw_input().split())
a.sort()

while(True):
    is_finish = False
    mn = min(a)
    while(a.count(mn) == 1):
        idx = a.index(mn)+1
        if idx >= len(a):
            mn = min(a)
            break
        else:
            mn = a[idx]

    mx = max(a)
    while(a.count(mx) == 1):
        idx = a.index(mx) - 1
        if idx < 0 or mx == mn :
            mx = max(a)
            is_finish = True
            break
        else :
            mx = a[idx]

    if is_finish :
        break
    else:
        a.remove(mn)
        a.remove(mx)

print len(a)


### FIXED CODE ###

N = int(raw_input())
a = set(map(int, raw_input().split()))
print len(a) if len(a) % 2 != 0 else len(a)-1