Медианой некоторого массива будем называть число, находящееся в его середине, если первоначально отсортировать данный массив в порядке неубывания. Если массив четной длины, то медианой является меньший из двух средних элементов. Например, пусть задан массив $$$[10, 3, 2, 3, 2]$$$, его медианой является число $$$3$$$ (т.е. $$$[2, 2, \underline{3}, 3, 10]$$$). У массива $$$[1, 5, 8, 1]$$$ медиана равна $$$1$$$ (т.е. $$$[1, \underline{1}, 5, 8]$$$).
Будем называть массив $$$m$$$-хорошим, если его медиана больше или равна $$$m$$$.
Разбиением массива $$$[a_1, a_2, \dots, a_n]$$$ будем называть такое множество массивов $$$\{b_1, b_2, \dots, b_k\}$$$, что $$$b_1 = [a_1, a_2, \dots, a_{i_1}]$$$, $$$b_2 = [a_{i_1 + 1}, a_{i_1 + 2}, \dots, a_{i_2}]$$$, ..., $$$b_k = [a_{i_{k-1} + 1}, a_{i_{k-1} + 2}, \dots, a_n]$$$. Например, массив $$$[10, 3, 2, 3, 2]$$$ можно разбить на $$$\{[10, 3, 2, 3, 2]\}$$$ или на $$$\{[10], [3], [2], [3], [2]\}$$$, или на $$$\{[10], [3, 2, 3, 2]\}$$$, или на $$$\{[10, 3], [2], [3, 2]\}$$$ и так далее.
Вам задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел, и целое число $$$m$$$. Найдите разбиение заданного массива $$$a$$$ на максимальное количество массивов, при этом каждый массив в разбиении должен быть $$$m$$$-хорошим.
В первой строке следуют два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 5\,000$$$, $$$1 \le m \le 5\,000$$$) — количество элементов в массиве $$$a$$$ и число $$$m$$$.
Во второй строке следует $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 5\,000$$$)— описание массива $$$a$$$.
Если невозможно разбить массив на $$$a$$$ на $$$m$$$-хорошие массивы, выведите $$$0$$$. В противном случае, выведите максимальное количество массивов в разбиении массива $$$a$$$, где каждый массив является $$$m$$$-хорошим.
5 2
10 3 2 3 2
5
5 3
10 3 2 3 2
1
5 4
10 3 2 3 2
0
В первом примере массив можно разбить на $$$5$$$ частей: $$$\{[10], [3], [2], [3], [2]\}$$$. Медиана каждой части не меньше $$$2$$$.
Во втором примере массив должен остаться неизменным, так как медиана массивов $$$[2]$$$, $$$[3, 2]$$$, $$$[2, 3, 2]$$$ и $$$[3, 2, 3, 2]$$$ меньше $$$3$$$.
| Название |
|---|


