有 $N$ 个按钮排成一排。相邻的按钮之间是相连的。

这些按钮内置了 LED 灯，总共可以显示 $C$ 种颜色。我们将这些颜色分别称为 $0$ 号颜色、$1$ 号颜色、……、$(C-1)$ 号颜色。

我们可以选择其中一个按钮并按下它。按下某个按钮后，与该按钮相连且颜色相同（设为颜色 $x$）的所有按钮的颜色都会变为 $(x+1)$ \% $C$ 号颜色。

例如，当 $N=5$，$C=4$ 时，假设按钮的初始颜色如下：

如果按下第 $4$ 个按钮，第 $4$ 个按钮的颜色将变为 $0$：

此后，如果按下第 $2$ 个按钮，第 $2, 3, 4$ 个按钮的颜色将变为 $1$：

再之后，如果按下第 $3$ 个按钮，第 $1, 2, 3, 4, 5$ 个按钮的颜色将变为 $2$：

如果我们不能选择两个或更多不同的按钮（但可以多次按下同一个按钮），请输出应该选择哪一个按钮，使得按下的次数最少，且能将所有按钮的颜色统一为同一种颜色。

输入格式

第一行包含两个空格分隔的整数：按钮的数量 $N$ $(1 \leq N \leq 250\,000)$ 和可能的颜色数 $C$ $(1\le C\le 10^9)$。

第二行包含 $N$ 个空格分隔的整数，表示每个按钮的颜色 $X_i$ ($0 \le X_i < C$)。

输出格式

第一行输出应该按下哪个按钮（最左边为 $1$，最右边为 $N$）。

第二行输出为了使所有按钮颜色相同，需要按下该按钮的最少次数。

如果存在多个能达到最少次数的按钮，输出其中最左边的按钮编号。

样例

输入样例 1

6 4
1 2 3 3 2 1

输出样例 1

3
6

输入样例 2

5 4
1 0 0 3 1

输出样例 2

4
2