No.2334 Distinct Cards
Problem Statement
There are $N$ cards. The $i$-th card ($1 \leq i \leq N$) has the integer $A_i$ written on it.
When taking $K$ cards from among them, find the minimum possible number of distinct integers written on the taken cards.
Input
The input is given from standard input in the following format.
$N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$
Output
Print the answer to standard output on $1$ line. End the output with a newline.
Constraints
The input satisfies the following constraints.
- $1 \leq N \leq 100\,000$
- $1 \leq K \leq N$
- $1 \leq A_i \leq N \ (1 \leq i \leq N)$
- All input values are integers.
Sample
Sample 1
Input
5 3 1 2 2 1 3
Output
2
If you take cards $1,2,3$, the integers written on the taken cards are $1, 2$, which is $2$ distinct integers.
It is impossible to take $3$ cards so that the integers written on the taken cards are $1$ distinct integer or fewer, so print $2$.
Sample 2
Input
4 4 1 2 3 4
Output
4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
SSRS
Kazun
Nachia