Problem A
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:

1. Divide the runes into $K$ groups of equal size.

2. 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.

3. 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\le N\le {10}^5$) and $K$ ($1\le K\le 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,\dots ,s_N(1\le s_i\le {10}^9)$ representing the strength of the runes.

Output

Output the number of possible core runes that exist.

9 3
1 1 2 3 5 8 13 21 34

3

6 3
4 4 4 4 4 4

6