$N$ buttons are arranged in a row. Each button is connected to its immediate neighbors.

These buttons have built-in LEDs and can display a total of $C$ different colors. We will refer to these colors as color $0$, color $1$, ..., color $(C-1)$.

We can choose to press any one button. When a button is pressed, all buttons connected to the pressed button that share the same color (let's call it color $x$) will change to color $(x+1) \pmod C$.

For example, suppose $N=5$ and $C=4$, and the buttons have the following colors:

If we press the 4th button, the color of the 4th button changes to $0$:

If we then press the 2nd button, the colors of buttons 2, 3, and 4 change to $1$:

If we then press the 3rd button, the colors of buttons 1, 2, 3, 4, and 5 change to $2$:

Given that we cannot press more than one button (though it is possible to press the same button multiple times), output which button should be chosen to minimize the number of presses required to make all buttons the same color.

Input

The first line contains the number of buttons $N$ $(1 \leq N \leq 250\,000)$ and the number of possible colors $C$ $(1 \le C \le 10^9)$, separated by a space.

The next line contains the color $X_i$ of each button $(0 \le X_i < C)$, separated by spaces.

Output

On the first line, output the index of the button to be pressed (the leftmost button is $1$, and the rightmost is $N$).

On the second line, output the minimum number of times that button must be pressed to make all buttons the same color.

If there are multiple buttons that result in the same minimum number of presses, output the index of the leftmost one.

Examples

Input 1

6 4
1 2 3 3 2 1

Output 1

3
6

Input 2

5 4
1 0 0 3 1

Output 2

4
2