16570번 - 앞뒤가 맞는 수열

수열 (a₁, a₂, ⋯, a_N) 이 다음의 성질을 가지면 그 수열은 k-앞뒤수열 이라고 한다.

(a₁, a₂, ⋯, a_k) = (a_N-k+1, a_N-k+2, ⋯ , a_N), 1 ≤ k < N

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

우리는 수열의 앞뒤가 맞게 만들기 위해 수열의 연속된 앞부분을 자를 수 있다.

예를 들어 (a₁, a₂, ⋯, a_N) 에서 (a₁, a₂) 을 제거하면 (a₃, a₄, ⋯ , a_N) 가 된다.

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

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

두번째 줄에 N개의 정수 A₁,A₂, ⋯ , A_N이 공백으로 구분되어 주어진다. (-2³¹ ≤ A_i ≤ 2³¹-1)

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