시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (언어별 추가 시간 없음) 128 MB 57 26 19 44.186%

문제

수열 (a1, a2, ⋯, aN) 이 다음의 성질을 가지면 그 수열은 k-앞뒤수열 이라고 한다.

(a1, a2, ⋯, ak) = (aN-k+1, aN-k+2, ⋯ , aN), 1 ≤ k < N

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

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

예를 들어 (a1, a2, ⋯, aN) 에서 (a1, a2) 을 제거하면 (a3, a4, ⋯ , aN) 가 된다.

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

입력

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

두번째 줄에 N개의 정수 A1,A2, ⋯ , AN이 공백으로 구분되어 주어진다. (-231 ≤ Ai ≤ 231-1)

출력

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

예제 입력 1

12
1 4 8 4 7 3 4 7 4 8 4 7

예제 출력 1

4 1

1 4 8 4 7 3 4 7 4 8 4 7

예제 입력 2

11
2 5 2 5 2 5 2 8 2 5 2

예제 출력 2

3 3

2 5 2 5 2 5 2 8 2 5 2

2 5 2 5 2 5 2 8 2 5 2

2 5 2 5 2 5 2 8 2 5 2

예제 입력 3

10
0 1 2 3 4 5 6 7 8 9

예제 출력 3

-1