Problem C
Arcane Secret
Viktor has developed a special formula to try and understand the secrets of the Arcane. He has $N$ runes where the $i$-th rune has a strength $s_i$. He wants to identify a core rune to study, but only certain runes can qualify.
He can identify a core rune with the following process:
-
Divide the runes into $K$ groups of equal size.
-
Take the maximum strength rune of every group and add it into a set $S$. If multiple runes within a group tie for the maximum strength, one of them is randomly added into $S$. Note that $S$ will have $K$ elements.
-
The rune whose strength is the median of $S$ is a core rune.
How many different runes can possibly be core runes?
Input
The first line of input contains $N$ ($1 \leq N \leq 10^5$) and $K$ ($1 \leq K \leq N$) representing the number of total runes and the number of groups that will be made. It is guaranteed that $K$ divides $N$ and $K$ is odd. The second line of input contains $N$ space separated integers $s_1, s_2, \ldots , s_N (1 \leq s_i \leq 10^9)$ representing the strength of the runes.
Output
Output the number of possible core runes that exist.
| Sample Input 1 | Sample Output 1 |
|---|---|
9 3 1 1 2 3 5 8 13 21 34 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 3 4 4 4 4 4 4 |
6 |
