/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
現在 AtCoder 高校には K 個のクラスと N 人の生徒が存在し、i 人目 (1\le i\le N) の生徒は A _ i 番目のクラスに所属しています。
高橋くんは 9 月から AtCoder 高校に転入することになりました。 高橋くんは、転入する際に K 個のクラスの中から好きなクラスを 1 つ選び、そのクラスに所属することができます。
高橋くんは、自分が所属しているクラスより多い人数が所属しているクラスがあるとき悲しみ、そうでないとき喜びます。
所属したときに高橋くんが喜ぶクラスがいくつあるか求めてください。
制約
- 1\le N\le2\times10 ^ 5
- 1\le K\le N
- 1\le A _ i\le K\ (1\le i\le N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A _ 1 A _ 2 \ldots A _ N
出力
条件を満たすクラスの個数を出力せよ。
入力例 1
8 5 3 3 5 5 4 4 3 2
出力例 1
3
例えば、高橋くんが 5 番目のクラスを選んで所属したとき、5 番目のクラスに所属している人数は 3 人となります。 このとき、3 人より多い人数が所属しているクラスは存在しないため、高橋くんは喜びます。
一方、例えば高橋くんが 1 番目のクラスを選んで所属したとき、1 番目のクラスに所属している人数は 1 人となります。 このとき、3 番目のクラスに所属している人数は 3 人なので、高橋くんは悲しみます。
3,4,5 番目のクラスを選んだとき、かつそのときに限り高橋くんは喜ぶので、3 を出力してください。
入力例 2
6 1 1 1 1 1 1 1
出力例 2
1
AtCoder 高校にクラスが 1 つしかない場合もあります。
入力例 3
14 8 6 1 5 3 8 4 3 4 3 5 1 2 5 1
出力例 3
4
Score : 300 points
Problem Statement
Currently, AtCoder High School has K classes and N students, and the i-th (1\le i\le N) student belongs to the A _ i-th class.
Takahashi is transferring to AtCoder High School in September. At that time, he can choose any one class among the K classes and belong to that class.
He will be sad if there is a class with more students belonging to it than the class he belongs to. Otherwise, he will be happy.
Find how many classes make him happy if he belongs to them.
Constraints
- 1\le N\le2\times10 ^ 5
- 1\le K\le N
- 1\le A _ i\le K\ (1\le i\le N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A _ 1 A _ 2 \ldots A _ N
Output
Output the number of classes satisfying the condition.
Sample Input 1
8 5 3 3 5 5 4 4 3 2
Sample Output 1
3
For example, if Takahashi chooses the fifth class and belongs to it, the number of students belonging to the fifth class becomes 3. Then, he will be happy since there is no class with more than three students belonging to it.
On the other hand, for example, if he chooses the first class and belongs to it, the number of students belonging to the first class becomes 1. Then, he will be sad since three students belong to the third class.
He will be happy if and only if he chooses the third, fourth, or fifth class, so output 3.
Sample Input 2
6 1 1 1 1 1 1 1
Sample Output 2
1
It is possible that AtCoder High School has only one class.
Sample Input 3
14 8 6 1 5 3 8 4 3 4 3 5 1 2 5 1
Sample Output 3
4