小红不想做鸽巢原理
题号:NC271809
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小红有n种不同颜色的小球,第i种颜色的小球有a_i个,放在同一个盒子中。

小红每次任意取出k个小球并丢弃,直到盒子中剩余的球数小于k个为止。

小红希望最终盒子里的小球颜色种类尽可能少,你能帮小红求出颜色的种类数量吗?

输入描述:

第一行输入两个正整数n,k,代表初始的颜色种类和小红每次丢弃的小球数量。
第二行输入n个正整数a_i,代表每种颜色的小球数量。
1\leq n \leq 10^5
1\leq k,a_i \leq 10^9

输出描述:

一个整数,代表最终剩余的颜色种类。
示例1

输入

复制
4 2
1 2 2 4

输出

复制
1

说明

小红可以操作4次,将第2、3、4三种小球全部丢弃。