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

import sys
# import collections
# import math
# import bisect
# import re
# import itertools


def primeNums(n):
    from math import floor, sqrt
    sieve = set(range(2, n + 1))
    if 2 in sieve:
        not_prime = set(range(2 * 2, n + 1, 2))
        sieve -= not_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            not_prime = set(range(i * 2, n + 1, i))
            sieve -= not_prime
    return sieve

limit = 10 ** 5
prime_table = [0 for _ in range(limit + 1)]
for p in primeNums(limit):
    prime_table[p] = 1

like_2017_table = [0 for _ in range(limit + 1)]
for i in range(3, limit + 1, 2):
    if prime_table[i] and prime_table[(i + 1) // 2]:
            like_2017_table[i] = 1

def main():

    q = int(sys.stdin.readline().rstrip())
    m = map(int, sys.stdin.read().split())

    for l, r in zip(m, m):
        res = sum(like_2017_table[l:r + 1])
        print(res)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
# import collections
# import math
# import bisect
# import re
# import itertools


def primeNums(n):
    from math import floor, sqrt
    sieve = set(range(2, n + 1))
    if 2 in sieve:
        not_prime = set(range(2 * 2, n + 1, 2))
        sieve -= not_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            not_prime = set(range(i * 2, n + 1, i))
            sieve -= not_prime
    return sieve

limit = 10 ** 5
prime_table = [0 for _ in range(limit + 1)]
for p in primeNums(limit):
    prime_table[p] = 1

like_2017_table = [0 for _ in range(limit + 1)]
for i in range(3, limit + 1, 2):
    if prime_table[i] and prime_table[(i + 1) // 2]:
            like_2017_table[i] = 1

s = [0 for _ in range(limit + 1)]
for i in range(limit):
    s[i+1] = s[i] + like_2017_table[i+1]

def main():

    q = int(sys.stdin.readline().rstrip())
    m = map(int, sys.stdin.read().split())

    for l, r in zip(m, m):
        res = s[r] - s[l-1]
        print(res)


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

def comb(n, r):
    if n == -1:
        n = 0
    return n*(n-1) // 2
n = int(input())
num_list =  list(map(int,input().split()))
num_list2 = [0]*n
num_list3 = [0]*n
for i in num_list:
    num_list2[i-1] += 1
for i in range(n):
    ans = comb(num_list2[i-1],2)
    num_list3[i-1] = ans

for i in num_list:
    ans = comb(num_list2[i-1]-1,2)
    print(ans-num_list3[i-1]+sum(num_list3))
  #  elif size == 1:
        #ans = 0
   # else :
    #    ans = 0 
    #num_list5[num_list2[i]-1] = ans


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = [0] * n
for i in a:
    cnt[i-1] += 1
total = [0] * n
for i in range(n):
    total[i] = cnt[i] * (cnt[i] - 1) // 2
total_sum = sum(total)
for i in a:
    ans = total_sum
    ans -= total[i-1]
    ans += (cnt[i-1] - 1) * (cnt[i-1] - 2) // 2
    print(ans)
### BUGGY CODE ###

import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

cons = 10 ** 6
is_prime = [True] * (cons + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(cons**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, cons + 1, i):
        is_prime[j] = False
Ps = [i for i in range(cons + 1) if is_prime[i]]

def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

pairwiseFlag = True

gcd = As[0]
for i in range(1, n):
  gcd = math.gcd(gcd, As[i])
setwiseFlag = (gcd == 1)

target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target = target | primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')


### FIXED CODE ###

import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

# cons = 10 ** 6
# is_prime = [True] * (cons + 1)
# is_prime[0] = False
# is_prime[1] = False
# for i in range(2, int(cons**0.5) + 1):
#     if not is_prime[i]:
#         continue
#     for j in range(i * 2, cons + 1, i):
#         is_prime[j] = False
# Ps = [i for i in range(cons + 1) if is_prime[i]]
def eratosthenes(n):
    is_prime = [0, 0] + [1] * (n - 1)
    for i in range(int(n**0.5) + 1):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i, pi in enumerate(is_prime) if pi == 1]
Ps = eratosthenes(10 ** 6)

def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target |= primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [input() for _ in range(n)]
prefix = set()
#out = dict()
for s in ss:
	u = ""
	for i in range(len(s)):
		u += s[i]
		prefix.add(u)
		#out[u] = 1
grundy = 0
for p in prefix:
	le = len(p)
	if p[le-1] == "0":
		t = p[:le-1] + "1"
	else:
		t = p[:le-1] + "0"
	if t not in prefix:
		grundy ^= (l-le+1) & (-l+le-1)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

### FIXED CODE ###

import sys
#from collections import defaultdict
sys.setrecursionlimit(10**6)

def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [list(input())[::-1] for _ in range(n)]

def addTree(tree, sentence):
	if not sentence:
		return None   

	if sentence[-1] not in tree:
		tree[sentence[-1]] = {}

	p = sentence.pop()
	tree[p] = addTree(tree[p], sentence)

	return tree

def createTree(sentences):    
	tree = {}
	for sentence in sentences:
		tree = addTree(tree, sentence)

	return tree

tree = createTree(ss)
#print(tree)

grundy = 0
def dfs(cur, level):
	global grundy
	if cur is None:
		return
	elif len(cur) == 1:
		grundy ^= (l-level) & (-l+level)
	for k in cur.keys():
		dfs(cur[k], level+1)
	return
	
dfs(tree, 0)

if grundy == 0:
	print("Bob")
else:
	print("Alice")
### BUGGY CODE ###

import itertools

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

def is_triangle(l):
    a, b, c = l
    if a < b + c and b < c + a and c < a + b :
        return 1
    else:
        return 0

ans = 0

for m in list(itertools.combinations(l,3)):
    ans += is_triangle(m)

print(ans)

### FIXED CODE ###

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

l.sort(reverse=True)

ans = 0

#1番長い辺(a)は固定する
for i in range(n - 2):
    #2番目に長い辺(b)＝次に長い辺とする
    j = i + 1
    #3番目の長さの辺(c)＝リストの中で最短の辺からスタート
    k = n - 1

    while j < k:
        #b<a+c,c<a+b は自明。a<b+cを判定する。
        #満たす場合、このbにおいて、cまでの全ての要素は条件を満たす(cが小さいほうから攻めているから)
        if l[i] < l[j] + l[k]:
            ans += k - j
            j += 1
        #満たさない場合、cを次に長い辺として再度判定。
        else:
            k -= 1

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

from collections import Counter

N=int(input())
D=Counter((list(map(int,input().split()))))
M=int(input())
T=Counter((list(map(int,input().split()))))

for i in range(len(D)):
    x=sorted([i for i in D.items()])

for j in range(len(T)):
    y=sorted([j for j in T.items()])

if N<M or len(x)<len(y):
    print("NO")
else:
    cnt=0
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i][0]==y[j][0] and x[i][1]>=y[j][1]:
                cnt+=1
    print("YES" if cnt==len(y) else "NO")

### FIXED CODE ###

from collections import Counter

N=int(input())
D=Counter((list(map(int,input().split()))))
M=int(input())
T=Counter((list(map(int,input().split()))))

for difficult,count in T.items():
    if difficult in D and D[difficult]>=count:
        pass
    else:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

N = int(input())
count = 0
P = list(map(int,input().split()))
for i in range(N):
    ok = True
    for j in range(i):
        if P[i] <= P[j]:
            None
        else:
            ok = False
            break
    if ok == True:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
count = 1
P = list(map(int,input().split()))
last_min = P[0]
for n in range(1,N):
    if last_min >= P[n]:
        count += 1
    last_min = min(last_min,P[n])
print(count)
### BUGGY CODE ###

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

ans = 0
for i in range(n):
  x = i+a[i]
  for j in range(x+1, n):
      if j - x == a[j]:
        ans += 1

print(ans)

### FIXED CODE ###

import numpy as np
from collections import Counter
n = int(input())
a = np.array(list(map(int, input().split())))
ni = np.array([i for i in range(n)])

ap = a + ni
an = (a - ni) * -1

cp = Counter(ap)
cn = Counter(an)

ans = 0
for i in cp.keys():
  ans += cp[i] * cn[i] 

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

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N = read()
A = []
for _ in range(N):
  A.append(reads())

necc = [[True] * N for _ in range(N)]

for i, j, k in combinations(range(N), 3):
  a, b, c = sorted((
    (A[i][j], i, j),
    (A[i][k], i, k),
    (A[j][k], j, k)
  ))
  if a[0] + b[0] < c[0]:
    print(-1); exit()
  elif a[0] + b[0] == c[0]:
    necc[c[1]][c[2]] = False

ans = sum(A[i][j] for i, j in combinations(range(N), 2) if necc[i][j])
print(ans)

### FIXED CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N = read()
A = []
for _ in range(N):
  A.append(reads())

necc = [[True] * N for _ in range(N)]

def fail():
  print(-1); exit()

for i, j, k in combinations(range(N), 3):
  if A[i][j] + A[j][k] < A[i][k] or A[i][j] + A[i][k] < A[j][k] or A[i][k] + A[j][k] < A[i][j]:
    fail()
  if A[i][j] + A[j][k] == A[i][k]:
    necc[i][k] = False
  if A[i][j] + A[i][k] == A[j][k]:
    necc[j][k] = False
  if A[i][k] + A[j][k] == A[i][j]:
    necc[i][j] = False

ans = sum(A[i][j] for i, j in combinations(range(N), 2) if necc[i][j])
print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[inf] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([inf] * (W + 2))
s.append(["#"] * (W + 2))
D.append([inf] * (W + 2))
visited = [[False] * (W + 2) for i in range(H + 2)]


def BFS():  # 幅優先探索(inf=>キュー=>訪問)
    global D
    D[1][1] = 1
    q = deque()
    q.append((1, 1))
    while len(q) != 0:
        p = q.popleft()
        visited[p[0]][p[1]] = True
        if p == (H, W):  # ゴールを訪問したら全部終わってなくても打ち切る
            return white_num - D[H][W]
        for e in [(p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0], p[1] - 1)]:
            if s[e[0]][e[1]] == "." and not visited[e[0]][e[1]]:
                D[e[0]][e[1]] = D[p[0]][p[1]] + 1
                q.append(e)
    return -1


print(BFS())

# for i in range(1, H + 1):
#    print(" ".join(list(map(str, D[i][1:-1]))))


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[inf] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([inf] * (W + 2))
s.append(["#"] * (W + 2))
D.append([inf] * (W + 2))


def BFS():  # 幅優先探索
    global D
    D[1][1] = 1
    q = deque()
    q.append((1, 1))
    while len(q) != 0:
        p = q.popleft()
        for e in [(p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0], p[1] - 1)]:
            if s[e[0]][e[1]] == "." and D[e[0]][e[1]] == inf:
                D[e[0]][e[1]] = D[p[0]][p[1]] + 1
                q.append(e)
                if e == (H, W):
                    return white_num - D[H][W]
    return -1


print(BFS())

# for i in range(1, H + 1):
#    print(" ".join(list(map(str, D[i][1:-1]))))
### BUGGY CODE ###

n = int(input())
n_list = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
num_list = [n % mod for n in n_list]
a_list = []
ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        a_list.append((num_list[i] * num_list[j]) % mod)

ans_list = [n % mod for n in a_list]

for i in range(len(ans_list)):
    ans += ans_list[i]
    ans = ans%mod

print (ans)

### FIXED CODE ###

n = int(input())
n_list = [int(i) for i in input().split()]

s = sum(a**2 for a in n_list)
ans = sum(n_list) ** 2 - s

print((ans//2)%(10**9+7))
### BUGGY CODE ###

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

# In[54]:


#import copy
import numpy as np

N, M = map(int, input().split())
As = np.array(sorted(list(map(int, input().split())), reverse=True))
"""
3 3
2 13 8

4 4
1 9 3 5
"""


# In[56]:


As[:9] = As[:9]


# In[57]:


As[0] = As[0] // 2
for i in range(1, M):
    As[:i+1] = np.sort(As[:i+1])[::-1]
    As[0] = As[0] // 2


# In[39]:


#print(As)
print(sum(As))


# In[ ]:






### FIXED CODE ###

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

# In[8]:


# import copy
#import numpy as np
import heapq

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

def int_minus(s):
    return -int(s)

As = list(map(int_minus, input().split()))
"""
3 3
2 13 8

4 4
1 9 3 5
"""


# In[10]:


heapq.heapify(As)


# In[17]:


for i in range(M):
    mx = heapq.heappop(As)
    heapq.heappush(As, -(-mx//2))


# In[19]:


#print(As)
print(-sum(As))


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

# coding: utf-8
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
p =list(map(int,input().split()))
pm = 0
for i in range(len(p) - k + 1):
  tmp = 0
  for j in range(k):
    tmp += p[i+j]
  pm = tmp if (tmp >= pm) else pm
ans = (pm + k) / 2
print(ans)

### FIXED CODE ###

# coding: utf-8
n, k = map(int, input().split())
p = list(map(int, input().split()))
pm = pp = sum(p[0:k])
for i in range(n - k):
    pp = pp - p[i] + p[k+i]
    pm = pp if (pp >= pm) else pm
ans = (pm + k) / 2
print(ans)
### BUGGY CODE ###


h,w,k=map(int,input().split())
maze=[input()for i in range(h)]

for i in range(h):
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j;break
    else:
        continue
    break
ans=float("INF")
l=[[float("INF")]*w for i in range(h)]
l[x][y]=0
from collections import deque
dq=deque([(x,y)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
p={(x,y)}
while len(dq):
    nx,ny=dq.popleft()
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=a+nx<h and 0<=ny+s<w and l[a+nx][s+ny]==float("INf")and maze[a+nx][s+ny]==".":
            l[a+nx][ny+s]=l[nx][ny]+1
            if l[a+nx][ny+s]<=k:p.add((a+nx,s+ny))
            if l[a+nx][ny+s]<k:dq.append((a+nx,s+ny))
ans=float("INf")

for x,y in p:
    ans=min(ans,(min(x,y,h-1-x,w-1-y)+k-1)//k+1)
print(ans)

### FIXED CODE ###


h,w,k=map(int,input().split())
maze=[]

for i in range(h):
    maze.append(input())
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j
    
ans=float("INF")
l=[[float("INF")]*w for i in range(h)]
l[x][y]=0
from collections import deque
dq=deque([(x,y)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
p={(x,y)}
while len(dq):
    nx,ny=dq.popleft()
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=a+nx<h and 0<=ny+s<w and l[a+nx][s+ny]==float("INf")and maze[a+nx][s+ny]==".":
            l[a+nx][ny+s]=l[nx][ny]+1
            if l[a+nx][ny+s]<=k:p.add((a+nx,s+ny))
            if l[a+nx][ny+s]<k:dq.append((a+nx,s+ny))
ans=float("INf")

for x,y in p:
    ans=min(ans,(min(x,y,h-1-x,w-1-y)+k-1)//k+1)
print(ans)
### BUGGY CODE ###

N = int(input())

A = []

for _ in range(N):
    a = int(input())
    if a in A:
        A.remove(a)
    else:
        A.append(a)

print(len(A))

### FIXED CODE ###

N = int(input())

A = set()

for _ in range(N):
    a = int(input())
    if a in A:
        A.remove(a)
    else:
        A.add(a)

print(len(A))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,p = [int(i) for i in input().split()]
s = input()
ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
    print(ans)
    exit()
    
else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i)+m)%p
    chk[m] += 1
  chk= [i*(i-1)/2 for i in chk]
  print(int(sum(chk)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,p = [int(i) for i in input().split()]
s = input()
ans = 0

import math
def nCr(n, r):
  if n < r:
    return 0
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
    print(ans)
    exit()

else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i,p)+m)%p
    chk[m] += 1
  for i in chk:
    ans += nCr(i,2)
  print(ans)
### BUGGY CODE ###

def f(a):
    if a % 2 == 0:
        return a // 2
    elif a % 2 == 1:
        return 3 * a + 1

s = int(input())
a = [s]
done = False
while not done:
    for i in range(len(a)):
        if a[i] != f(a[-1]):
            a.append(f(a[-1]))

        else:
            print(i)
            done = True
            break


### FIXED CODE ###

def f(n):
    if n % 2 == 0:
        return n // 2
    elif n % 2 == 1:
        return 3 * n + 1


s = int(input())
a = [s]
done = False
while not done:
    if f(a[-1]) in a:
        print(len(a) + 1)
        done = True
        break
    else:
        a.append(f(a[-1]))
### BUGGY CODE ###

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

c1 = []
c2 = []
cumv = 0
for x,v in src:
    cumv += v
    c1.append(cumv - x)
    c2.append(cumv - 2*x)

r1 = []
r2 = []
cumv = 0
for x,v in reversed(src):
    cumv += v
    x = C-x
    r1.append(cumv - x)
    r2.append(cumv - 2*x)

ans = max(c1+r1+[0])
for i,c in enumerate(c2):
    for r in r1[:N-i-1]:
        ans = max(ans, c+r)
for i,r in enumerate(r2):
    for c in c1[:N-i-1]:
        ans = max(ans, c+r)

print(ans)


### FIXED CODE ###

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

c1 = []
c2 = []
c1x = []
cumv = 0
c1max = -float('inf')
for x,v in src:
    cumv += v
    c1.append(cumv - x)
    c2.append(cumv - 2*x)
    c1max = max(c1max, c1[-1])
    c1x.append(c1max)

r1 = []
r2 = []
r1x = []
cumv = 0
r1max = -float('inf')
for x,v in reversed(src):
    cumv += v
    x = C-x
    r1.append(cumv - x)
    r2.append(cumv - 2*x)
    r1max = max(r1max, r1[-1])
    r1x.append(r1max)

ans = max(c1+r1+[0])
for i,c in enumerate(c2[:-1]):
    ans = max(ans, c + r1x[N-i-2])
for i,r in enumerate(r2[:-1]):
    ans = max(ans, r + c1x[N-i-2])

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

ans=0
n=int(input())
li=list(map(int,input().split()))
for i in range(1,n):
    k=sum(li[:i])
    ans+=k*li[i]
print(ans%(10**9+7))

### FIXED CODE ###

import itertools
ans=0
n=int(input())
li=list(map(int,input().split()))
L=list(itertools.accumulate(li))
for i in range(1,n):
    ans+=L[i-1]*li[i]
print(ans%(10**9+7))
### BUGGY CODE ###

import itertools

N,M,R = map(int, input().split())
r = map(int, input().split())
l = [[1e9 for i in range(N+1)] for i in range(N+1)]

for i in range(M):
    a,b,c = map(int, input().split())
    l[a][b] = l[b][a] = c

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            t = l[i][k] + l[k][j]
            if l[i][j] > t: l[i][j] = t

ans = 1e9
for a in itertools.permutations(r):
    s = 0
    for i,j in zip(a[:-1],a[1:]):
        s += l[i][j]
    if ans > s: ans = s

print(ans)


### FIXED CODE ###

import itertools

N,M,R = map(int, input().split())
r = map(int, input().split())
l = [[1e9 for i in range(N+1)] for i in range(N+1)]

for i in range(M):
    a,b,c = map(int, input().split())
    l[a][b] = l[b][a] = c

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            t = l[i][k] + l[k][j]
            if l[i][j] > t: l[i][j] = t

ans = 1e9
for a in itertools.permutations(r):
    s = 0
    for i,j in zip(a[:-1],a[1:]):
        s += l[i][j]
    if ans > s: ans = s

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

import sys

stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def ns(): return stdin.readline().strip()
def ni(): return int(stdin.readline())

n = ni()
a = na()
lst = []
c=0
for i in a:
    if(i not in lst):
        lst.append(i)
        c = c+1

if(c%2 == 0):c=c-1

print(c)


### FIXED CODE ###

import sys

stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def ns(): return stdin.readline().strip()
def ni(): return int(stdin.readline())

n = ni()
a = na()
st = set()
for i in a:
    if(i not in st):
        st.add(i)

c = len(st)
if(c%2 == 0):c=c-1

print(c)
### BUGGY CODE ###

A, B, N = map(int,input().split())
score = 0
for i in range(int(N//1.5) ,N):
    x = i+1
    val = int(A*x/B) - A * int(x/B)
    #print( int(A*x/B) , A * int(x/B))
    if(val > score):
        score = val
print(score)


### FIXED CODE ###

A, B, N = map(int,input().split())
x = min(N,B-1)
val = int(A*x/B) - A * int(x/B)
print(val)