题目描述
现有一个已排序的整数数组 ai。可以对该数组进行任意次以下操作:
- 将所有不等于其左侧相邻元素的元素(即 ai=ai−1 的 i),以及第一个元素(即 i=1),设定为已标记。
- 删除所有已标记的元素,或在原位置复制一遍它们。
例如,对于数组 [1,1,1,2,4,4,5],其第 1,4,5,7 个元素是已标记的。
- 若删除所有标记元素,则得到 [1,1,4]。
- 若复制这些标记元素,则得到 [1,1,1,1,2,2,4,4,4,5,5]。
若数组为空,则无法执行操作。每次操作后,所有元素均会被取消标记。
我们称一个整数数组 b 为可达的,当且仅当可以通过若干次所述操作,从数组 a 获得。
请统计长度为 k 的可达数组的数量。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数 a1,a2,…,an。保证该数组已排序。
输出格式
输出一个整数,表示长度为 k 的可达数组的数量。
样例 1 输入
3 3
2 2 3
样例 1 输出
2
样例 2 输入
10 7
1 1 1 2 2 3 3 3 3 4
样例 2 输出
2
数据范围
对于所有测试数据,保证:1≤n,k≤3×105,1≤a1≤a2≤⋯≤an≤n。
| 测试点 |
n≤ |
特殊性质 |
| 1∼4 |
5 |
无 |
| 5∼6 |
100 |
| 7∼10 |
1000 |
| 11∼12 |
3×105 |
k≤10 |
| 13∼14 |
an≤100 |
| 15∼20 |
无 |