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

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

MOD = 10**9 + 7
MAX = n + 5
fact = [1 for _ in range(MAX)]
finv = [1 for _ in range(MAX)]
for i in range(2, MAX):
    fact[i] = fact[i - 1] * i % MOD
    finv[i] = pow(fact[i], MOD-2, MOD)

def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n-k] % MOD


d = defaultdict(list)
for i in range(n+1):
    d[a[i]].append(i)
    if len(d[a[i]]) == 2:
        i1, i2 = sorted(d[a[i]])
        m1 = i1
        m2 = i2 - i1 - 1
        m3 = n - i2

# print((i1, i2), m1, m2, m3)

ans = [n]
if n > 1:
    ans.append(comb(m1+m2+m3, 2) + m1+m2 + m2+m3 + 1)
for k in range(3, n+1):
    ansi = comb(n+1, k)
    for l in range(k):
        ansi -= comb(m1, l) * comb(m3, k-1-l)
        ansi = (ansi + MOD) % MOD

    ans.append(ansi)

ans.append(1)

for ansi in ans:
    print(ansi)


### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

MOD = 10**9 + 7
MAX = n + 5
fact = [1 for _ in range(MAX)]
finv = [1 for _ in range(MAX)]
for i in range(2, MAX):
    fact[i] = fact[i - 1] * i % MOD
    finv[i] = pow(fact[i], MOD-2, MOD)

def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n-k] % MOD


d = defaultdict(list)
for i in range(n+1):
    d[a[i]].append(i)
    if len(d[a[i]]) == 2:
        i1, i2 = sorted(d[a[i]])
        m1 = i1
        m2 = i2 - i1 - 1
        m3 = n - i2

# print((i1, i2), m1, m2, m3)
ans = []
for k in range(1, n+2):
    ansi = comb(n+1, k) - comb(m1+m3, k-1)
    ansi = (ansi + MOD) % MOD
    ans.append(ansi)

for ansi in ans:
    print(ansi)
### BUGGY CODE ###

n = int(input())

if n == 1:
    print(0)
    exit()
elif n == 2:
    print(1)
    exit()

ans = 0
for i in range(1, n):
    ans += i

print(ans)


### FIXED CODE ###

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

n = int(input())

li_a = list(map(int, input().split()))

sm = sum(li_a)
result = -1
for c in range(1, len(li_a)):
    x = sum(li_a[0:c])
    y = sm - x
    result = min(result, abs(x - y)) if result >= 0 else abs(x - y)

print(result)

### FIXED CODE ###

n = int(input())

li_a = list(map(int, input().split()))

sm = sum(li_a)

li_ruiseki = list()

for a in li_a:
    if len(li_ruiseki) == 0:
        li_ruiseki.append(a)
    else:
        li_ruiseki.append(li_ruiseki[-1] + a)

result = -1
for x in li_ruiseki[:-1]:
    a = abs(sm - 2 * x)
    result = min(result, a) if result >= 0 else a

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

import sys
input = sys.stdin.readline
def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[[xs,ys,0],[xt,yt,0]]
  xyr+=[list(map(int,input().split())) for _ in range(n)]
  memo={}
  def dist(i,j):
    if i<j:
      i,j=j,i
    if (i,j) in memo:return memo[(i,j)]
    x,y,r=xyr[i]
    x1,y1,r1=xyr[j]
    d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
    memo[(i,j)]=d
    return d
  from heapq import heappop,heappush
  todo=[[0,0]]
  ka=set(())
  seen=[-1]*(n+2)
  seen[0]=0
  while todo:
    d,v=heappop(todo)
    if v in ka:continue
    if v==1:
      print(d)
      exit()
    ka.add(v)
    for nv in range(n+2):
      if v==nv or nv in ka:continue
      nd=dist(v,nv)
      if seen[nv]==-1 or seen[nv]>d+nd:
        heappush(todo,[d+nd,nv])
        seen[nv]=d+nd
if __name__=='__main__':
  main()


### FIXED CODE ###

from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [tuple(list(map(int, input().split())) + [i]) for i in range(q)]


bit = BIT(n)
memo = {}
ans = [0] * q
query.sort(key=itemgetter(1))
ind = 0

for l, r, i in query:
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

print("\n".join(map(str, ans)))


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [list(map(int, input().split())) + [i] for i in range(q)]


bit = BIT(n)
memo = {}
ans = [0] * q
query = sorted(query, key=itemgetter(1))
ind = 0

for l, r, i in query:
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

print("\n".join(map(str, ans)))
### BUGGY CODE ###

s=input()
k=int(input())
d=dict()
if len(s)==1:
  print(s)
else:
  for i in range(len(s)):
    a=s[i]
    if a not in d:
      d[a]=0
    for j in range(i+1,len(s)):
      a+=s[j]
      if a not in d:
        d[a]=0
  l=list(d)
  l.sort()
  print(l[k-1])

### FIXED CODE ###

s=input()
k=int(input())
n=len(s)
ans=dict()
for i in range(n):
  t=str()
  for j in range(min(5,n-i)):
    t+=s[i+j]
    ans[t]=0
ans=sorted(list(ans.keys()))
print(ans[k-1])
### BUGGY CODE ###

N,Q=map(int, input().split())
S=input()
for i in range(Q):
  l,r=map(int, input().split())
  print(S[l-1:r].count("AC"))

### FIXED CODE ###

N,Q=map(int, input().split())
S=input()
list=[0]*N
#計算量が多いので、さきに文字列のACの数を数えておく。
for i in range(1,N):
  if S[i-1:i+1]=="AC":
    list[i]=list[i-1]+1
  else:
    list[i]=list[i-1]
for i in range(Q):
  l,r=map(int,input().split())
  print(list[r-1]-list[l-1])
### BUGGY CODE ###

a = input()
a = int(a)
b = input()
b= b.rstrip().split(" ")

#print(b)

b1=[]
for i in range(len(b)):
    b1.append(int(b[i]))
    i +=1
    
#print(b1)

list2=[]
for j in range(len(b1)):
    list1=[]
    for k in range(len(b1)):
        if j == k :
            k +=1
        else:
            list1.append(b1[k])
            k+=1
    list3=sorted(list1)
    list2.append(list3)
    j +=1
#print(list2)

for l in range(int(a)):
    print(list2[l][int(a/2)-1])
    l+=1

### FIXED CODE ###

a = input()
a = int(a)
b = input()
b= b.rstrip().split(" ")

bi =[]
for i in range(len(b)):
    bi.append(int(b[i]))
    i+=1
    
#print(bi)
bs =sorted(bi)
#print(bs)
for j in range(int(a)):
    if bi[j]>=bs[int(len(bs)/2)]:
        print(bs[int(len(bs)/2-1)])
        j+=1
    else:
        print(bs[int(len(bs)/2)])
        j+=1
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]

    INF = float('INF')
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            #bipas = min(map(sum, zip(A[i], A[j])))
            bipas = 10**10
            for k in range(N):
                bipas = min(bipas, A[i][k] + A[j][k])

            if A[i][j] > bipas:
                ans = -1
                break
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N = int(input())
    A = np.array([list(map(int, input().split())) for i in range(N)])
    #A = [list(map(int, input().split())) for _ in range(N)]
    #A = np.array(A)

    INF = 10**10
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            #bipas = min(map(sum, zip(A[i], A[j])))
            bipas = np.min(A[i] + A[j])

            if A[i][j] > bipas:
                print(-1)
                return 0
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


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

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
  if x>s:
    break
  for y in range(k+1):
    if x+y>s:
      break
    if s-(x+y)>=0 and s-(x+y)<=k:
      cnt+=1
print(cnt)


### FIXED CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
  if s-x<0:
    break
  elif s-x<=k:
    cnt+=(s-x)+1
  elif s-x>2*k:
    cnt+=0
  elif s-x>k:
    cnt+=2*k-(s-x)+1
print(cnt)
### BUGGY CODE ###

S = input()

num = 0
while True:
    p = S.find('01')
    if p > -1:
        S = S[:p] + S[p + 2:]
        num += 2
    else:
        break
while True:
    p = S.find('10')
    if p > -1:
        S = S[:p] + S[p + 2:]
        num += 2
    else:
        print(num)
        break


### FIXED CODE ###

S = input()
print(min(S.count('0'), S.count('1')) * 2)
### BUGGY CODE ###

n = int(input())
a = list(int(input()) for _ in range(n))

paper = []
for i in a:
    if i in paper:
        paper.remove(i)
    else:
        paper.append(i)
print(len(paper))


### FIXED CODE ###

from collections import Counter

n = int(input())
a = [int(input()) for _ in range(n)]

a_c = Counter(a).most_common() 
ans = 0
for i in a_c: 
    if i[1] % 2 == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

from math import ceil
from bisect import bisect_right

def update(x, v):
  while x <= N:
    fw[x] += v
    x += x & -x

def s(x):
  res = 0
  while x:
    res += fw[x]
    x -= x & -x
  return res


N,D,A = map(int,input().split())
monsters = sorted([list(map(int,input().split())) for _ in range(N)])

fw = [0 for _ in range(N + 1)]

ans = 0
for i in range(N):
  h = s(i + 1) - s(0)
  if monsters[i][1] + h > 0:
    num_bomb = ceil((monsters[i][1] + h) / A)
    ans += num_bomb

    k = bisect_right(monsters, [monsters[i][0] + 2*D, 10**9])
    update(i + 1, -(num_bomb * A))
    update(k + 1, num_bomb * A)
    
print(ans)


### FIXED CODE ###

from math import ceil
from collections import deque

N,D,A = map(int,input().split())
monsters = sorted([list(map(int,input().split())) for _ in range(N)])

q = deque([])
s = 0

ans = 0
for i in range(N):
  while len(q) > 0 and q[0][0] < monsters[i][0]:
    s -= q[0][1]
    q.popleft()

  h = monsters[i][1] - s * A
  if h > 0:
    num_bombs = ceil(h / A)

    q.append((monsters[i][0] + 2 * D, num_bombs))
    s += num_bombs
    ans += num_bombs
    
print(ans)
### BUGGY CODE ###

import heapq

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

INF = float('inf')

def dijkstra(s, g, key):
    dist = [INF for i in range(n)]
    dist[s] = 0
    hq2 = [(0, s)]
    while hq2:
        cost, node = heapq.heappop(hq2)
        if cost > dist[node]:
            continue
        for v_next, d_next in enumerate(graph[node]):
            if d_next == INF:
                continue
            d = d_next + cost
            if d < dist[v_next]:
                dist[v_next] = d
                heapq.heappush(hq2, (dist[v_next], v_next))
    if dist[g] > key:
        graph[s][g] = key
        graph[g][s] = key
        return key
    elif dist[g] == key:
        return 0
    else:
        return -1

ans = 0
hq = []
for i in range(n-1):
    for j in range(i+1, n):
        heapq.heappush(hq, (a[i][j], i, j))

graph = [[INF for i in range(n)] for j in range(n)]

while hq:
    dist, vs, vg = heapq.heappop(hq)
    flag = dijkstra(vs, vg, dist)
    if flag == -1:
        break
    else:
        ans += flag
if flag == -1:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

INF = float('inf')
graph = [[INF for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        graph[i][j] = a[i][j]

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(n):
    for j in range(n):
        if graph[i][j] < a[i][j]:
            print(-1)
            exit()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        v = INF
        for k in range(n):
            if k == i or k == j:
                continue
            v = min(v, graph[i][k] + graph[k][j])
        if v != graph[i][j]:
            ans += graph[i][j]

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

if __name__ == '__main__':
	S = input()
	Q = int(input())

	c = 1

	for i in range(Q):
		I = input()
		if len(I) == 1:
			c = c * (-1)
		else:
			T, F, C = I.split()
			f = int(F)
			if f == 1 and c == 1:
				S = C + S
			elif f == 1 and c == -1:
				S = S + C
			elif f == 2 and c == -1:
				S = C + S
			else:
				S = S + C

	if c == -1:
		S = S[::-1]

	print(S)

### FIXED CODE ###

if __name__ == '__main__':
	S = input()
	Q = int(input())

	c = 1

	A = ''
	B = ''

	for i in range(Q):
		I = input()
		if len(I) == 1:
			c = c * (-1)
		else:
			T, F, C = I.split()
			f = int(F)
			if f == 1 and c == 1:
				A = C + A
			elif f == 1 and c == -1:
				B = B + C
			elif f == 2 and c == -1:
				A = C + A
			else:
				B = B + C

	S = A + S + B

	if c == -1:
		S = S[::-1]

	print(S)
### BUGGY CODE ###

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

arr = [N,0,0,0,0]
count = 0

while True:
    count += 1
    arr[4] =max(0,arr[4]-E)
    arr[4] +=min(D,arr[3])

    arr[3] =max(0,arr[3]-D)
    arr[3] +=min(C,arr[2])

    arr[2] =max(0,arr[2]-C)
    arr[2] +=min(B,arr[1])

    arr[1] =max(0,arr[1]-B)
    arr[1] +=min(A,arr[0])

    arr[0] =max(0,arr[0]-A)
    if sum(arr) == 0:
        break

print(count)

### FIXED CODE ###

import math
N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

print(math.ceil(N/min(A,B,C,D,E))+4)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
B1 = [0 for i in range(60)]
B0 = [0 for i in range(60)]
for x in A:
    bA = format(x,"b").zfill(60)
    for i in range(60):
        if bA[i] == "1":
            B1[i] += 1
        elif bA[i] == "0":
            B0[i] += 1
ans = 0
for i in range(60):
    ans = (ans + 2**(59-i)*B1[i]*B0[i]) % (10**9+7)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
B1 = [0 for i in range(60)]
B0 = [0 for i in range(60)]
for x in A:
    bA = format(x,"b").zfill(60)
    for i in range(60):
        if bA[i] == "1":
            B1[i] += 1
        elif bA[i] == "0":
            B0[i] += 1
ans = 0
for i in range(60):
    ans = (ans + 2**(59-i)*B1[i]*B0[i]) % (10**9+7)
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
def ans(l):
    max = 0
    b = set(l)
    for i in b:
        s = l.count(i)
        if s>max:
            max = s
    return n/2 - max
if len(set(a)) == 1:
    p = int(n/2)
else:
    p = int(ans(a[::2]) + ans(a[1::2]))
print(p)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]

if len(set(a)) == 1:
    p = int(n/2)
else:
    b0 = set(a[::2])
    if len(b0)==1:
        q0 = 0
        mark00 = a[0]
        count00, count01 = int(n/2), 0
    else:
        c = Counter(a[::2])
        q0 =  int(n/2) - c.most_common(1)[0][1]
        mark00, mark01 = c.most_common(2)[0][0], c.most_common(2)[1][0]
        count00, count01 = c.most_common(2)[0][1], c.most_common(2)[1][1]

    b1 = set(a[1::2])
    if len(b1)==1:
        q1 = 0
        mark10 = a[1]
        count10, count11 = int(n/2), 0
    else:
        c = Counter(a[1::2])
        q1 =  int(n/2) - c.most_common(1)[0][1]
        mark10, mark11 = c.most_common(2)[0][0], c.most_common(2)[1][0]
        count10, count11 = c.most_common(2)[0][1], c.most_common(2)[1][1]
    if mark00==mark10:
        if count00+count01>count10+count11:
            p = n - (count00+count01)
        else:
            p = n - (count10+count11)
    else:
        p = n - (count00 + count10)

print(p)
### BUGGY CODE ###


import copy


class MyClass():

    maxSum = 0

    def do(self, baseList, _temochi, leftIndex, rightIndex, nokoriSousaCount):
        if nokoriSousaCount < 0:
            return

        sum = 0
        for each in _temochi:
            sum += each

        if self.maxSum < sum:
            self.maxSum = sum

        if leftIndex <= rightIndex:
            temochi = copy.copy(_temochi)
            temochi.append(baseList[leftIndex])
            self.do(baseList, temochi, leftIndex + 1, rightIndex, nokoriSousaCount - 1)

            temochi = copy.copy(_temochi)
            temochi.append(baseList[rightIndex])
            self.do(baseList, temochi, leftIndex, rightIndex - 1, nokoriSousaCount - 1)
            
        self.removeMin(_temochi, leftIndex, rightIndex, nokoriSousaCount - 1)

    def removeMin(self, _temochi, leftIndex, rightIndex, nokoriSousaCount):
        if len(_temochi) > 0 and nokoriSousaCount > 0:
            minNum = min(_temochi)
            if minNum < 0:
                temochi = copy.copy(_temochi)
                temochi.remove(minNum)
                self.do(baseList, temochi, leftIndex, rightIndex, nokoriSousaCount)


count, opeCount = map(int, input().split())
baseList = list(map(int, input().split()))

doClass = MyClass()
doClass.do(baseList, [], 0, count - 1, opeCount)

print(doClass.maxSum)




### FIXED CODE ###

class MyClass():
    maxNumber = 0

    def roop(self, baseList, opeCount):
        listCount = len(baseList)
        roopMax = listCount if listCount < opeCount else opeCount
        for leftCount in range(0, roopMax):
            self.getMax(baseList[0: leftCount + 1], opeCount - leftCount - 1)

            for rightCount in range(1, roopMax - leftCount + 1):
                leftList = baseList[0: leftCount]
                rightList = baseList[listCount - rightCount : listCount]
                handList = leftList + rightList

                self.getMax(handList, opeCount - leftCount - rightCount)

                

    def getMax(self, handList, remainOpeCount):
        if len(handList) < 1:
            return

        maxVal = 0
        removeCount = 0

        if remainOpeCount > 0:
            handList.sort()
            for each in handList:
                if each < 0:
                    removeCount += 1
                    remainOpeCount -= 1
                    if remainOpeCount < 1:
                        break
        
        maxVal = sum(handList[removeCount:])
        self.maxNumber = max([maxVal, self.maxNumber])


count, opeCount = map(int, input().split())
baseList = list(map(int, input().split()))

my = MyClass()
my.roop(baseList, opeCount)
print(my.maxNumber)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
li = list(set(a))
a.sort()
li.sort()
count = 0
for i in range(len(li)):
    if a.count(li[i]) > li[i]:
        count += a.count(li[i])-li[i]
    elif li[i] > a.count(li[i]):
        count += a.count(li[i])
print(count)


### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int,input().split()))
A = Counter(A)
keys = list(A.keys())
count = 0
for i in range(len(A)):
    if keys[i]!=A[keys[i]]:
        if keys[i]>A[keys[i]]:
            count += A[keys[i]]
        else:
            count += A[keys[i]]-keys[i]
print(count)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    visited = [False for i in range(n)]
    color_used = [set() for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, color_used, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    for j in adjs[i]:
        if visited[j]:
            continue
        for c in range(1, 100005):
            if c in color_used[i]:
                continue
            if c in color_used[j]:
                continue
            color_used[i].add(c)
            color_used[j].add(c)
            mi = min(i, j)
            ma = max(i, j)
            colors[(mi, ma)] = c
            break
        dfs(j, adjs, visited, color_used, colors)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import random

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    for i in range(n):
        random.shuffle(adjs[i])
    visited = [False for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, -1, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    c = 1
    for j in adjs[i]:
        if visited[j]:
            continue
        if c == color_used:
            c += 1
        mi = min(i, j)
        ma = max(i, j)
        colors[(mi, ma)] = c
        dfs(j, adjs, visited, c, colors)
        c += 1

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

a,b,n=map(int,input().split())
m=0
if n<b:
	m=(a*n)//b
elif n==b:
	m=max((a*(n-1))//b,(a*n)//b-a*(n//b))
else:
	m=(a*(n-1))//b
	for i in range(b,n+1):
		m=max(m,(a*n)//b-a*(n//b))
print(m)


### FIXED CODE ###

a,b,n=map(int,input().split())
m=0
if n<b:
	m=(a*n)//b
elif n==b:
	m=max((a*(n-1))//b,(a*n)//b-a*(n//b))
else:
	m=max((a*(b-1))//b,(a*n)//b-a*(n//b))
print(m)