앞뒤가 맞는 수열

수열 $(a_1, a_2, \cdots, a_N)$이 다음 성질을 가지면 그 수열을 k-앞뒤수열이라고 한다.

$(a_1, a_2, \cdots, a_k) = (a_{N-k+1}, a_{N-k+2}, \cdots, a_N), \quad 1 \le k < N$

어떤 수열이 k-앞뒤수열일 때, k의 최댓값 $k^*$를 그 수열의 앞뒤계수라고 한다.

수열의 앞뒤를 맞추기 위해 수열의 연속된 앞부분을 잘라낼 수 있다.

예를 들어 $(a_1, a_2, \cdots, a_N)$에서 $(a_1, a_2)$를 제거하면 $(a_3, a_4, \cdots, a_N)$이 된다.

주어진 수열 $(A_1, A_2, \cdots, A_N)$의 앞부분을 얼마나 잘라야 앞뒤계수를 최대로 만들 수 있을까? 단, 그러한 방법은 2가지 이상일 수 있다. 그리고 자르는 방법에는 "아무것도 자르지 않는 것"도 포함한다.

첫 번째 줄에 $N$이 주어진다. ($2 \le N \le 1\,000\,000$)

두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($-2^{31} \le A_i \le 2^{31}-1$)

앞부분을 잘라서 앞뒤수열로 만들 수 있다면, 그렇게 자른 후 수열의 앞뒤계수 최댓값과 그렇게 자르는 방법의 수를 공백으로 구분하여 출력한다. 어떻게 잘라도 앞뒤계수가 존재하지 않으면 -1을 출력한다.