$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$로 바뀌게 된다.

우리가 $2$개 이상의 버튼들을 누를 수 없다고 했을 때(한 버튼을 여러번 누르는 것은 가능하다), 어떤 버튼을 선택해야 누른 횟수를 최소로 하며 모든 버튼의 색을 같은 색으로 통일시킬 수 있는지 출력하라.

Input

첫 번째 줄에 버튼의 수 $N$ $(1 \leq N \leq 250\,000)$ 과 가능한 색의 수 $C$ $(1\le C\le 10^9)$가 공백으로 구분되어 주어진다.

다음 줄에 각 버튼의 색 $X_i$ ($0 \le X_i < C$)가 공백으로 구분되어 주어진다.

Output

첫 번째 줄에 몇 번 버튼을 눌러야 하는지 출력한다(가장 왼쪽이 $1$, 가장 오른쪽이 $N$이다).

두 번째 줄에 모든 버튼을 같은 색으로 통일시키기 위해 그 버튼을 눌러야 할 횟수를 출력한다.

만약 최소 횟수가 되는 버튼이 여러 개 존재한다면 그 중 가장 왼쪽의 버튼을 출력한다.

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