Viktor 研发了一种特殊的配方，试图理解奥术（Arcane）的秘密。他有 $N$ 个符文，其中第 $i$ 个符文的强度为 $s_i$。他想选出一个核心符文进行研究，但只有特定的符文才符合条件。

他可以通过以下步骤来确定一个核心符文：

1. 将这些符文分成 $K$ 个大小相等的组。
2. 找出每组中强度最大的符文，并将其加入集合 $S$。如果一个组内有多个符文并列最大强度，则随机选择其中一个加入 $S$。注意，$S$ 将包含 $K$ 个元素。
3. 强度为 $S$ 中中位数的符文即为核心符文。

有多少个不同的符文有可能成为核心符文？

输入格式

第一行输入包含两个整数 $N$ ($1 \le N \le 10^5$) 和 $K$ ($1 \le K \le N$)，分别表示符文的总数和要分成的组数。保证 $K$ 整除 $N$ 且 $K$ 为奇数。

第二行输入包含 $N$ 个空格分隔的整数 $s_1, s_2, \dots, s_N$ ($1 \le s_i \le 10^9$)，表示每个符文的强度。

输出格式

输出可能成为核心符文的不同的符文数量。

样例

样例输入 1

9 3
1 1 2 3 5 8 13 21 34

样例输出 1

3

样例输入 2

6 3
4 4 4 4 4 4

样例输出 2

6