세 자리의 평탄한 야영 구역

문제

캠핑장에는 일직선 산책로를 따라 N개의 야영 자리가 놓여 있다. 각 자리에는 산책로의 한쪽 끝부터 차례대로 1번부터 N번까지 번호가 붙어 있다. 관리인은 작은 단체가 함께 사용할 구역을 정하려고 한다. 단체는 텐트 세 동을 가져오므로, 번호가 연속한 자리 세 개를 하나의 구역으로 골라야 한다. 산책로의 양 끝은 이어져 있지 않으므로 N번 자리 다음에 1번 자리가 있다고 생각해서는 안 된다. 각 자리의 상태는 정수 하나로 주어진다. 값이 0이면 정비 중이라 사용할 수 없는 자리다. 값이 1 이상 9 이하이면 사용할 수 있으며, 그 값은 공통 기준면에서 측정한 바닥의 높이를 뜻한다. 정비 중인 자리가 하나라도 포함된 구역은 후보에서 제외한다. 정비 중인 자리를 건너뛰어 세 자리를 고르거나, 서로 떨어진 자리를 묶는 것은 허용하지 않는다. 단체는 텐트 사이를 편하게 오갈 수 있도록 세 자리의 높이가 비슷한 구역을 원한다. 후보 구역의 높이 차이는 그 구역에 있는 세 높이 중 최댓값에서 최솟값을 뺀 값이다. 관리인은 먼저 높이 차이가 가장 작은 후보를 고른다. 높이 차이가 같은 후보가 여러 개라면, 세 높이의 합이 가장 큰 후보를 고른다. 높이 차이와 높이의 합까지 모두 같다면, 시작 자리의 번호가 가장 작은 후보를 고른다. 이 우선순위는 적힌 순서대로 적용하며, 뒤의 조건이 앞의 조건보다 우선할 수는 없다. 구역의 시작 번호가 s라면 그 구역은 s번, s+1번, s+2번 자리로 이루어진다. 높이가 같은 자리들도 서로 다른 자리이므로 각각 한 자리로 센다. 모든 가능한 시작 번호를 살펴보고 위 규칙으로 결정되는 구역의 시작 번호를 구해야 한다. 사용할 수 있는 연속한 자리 세 개가 전혀 없으면 구역을 정할 수 없다.

입력

첫째 줄에 야영 자리의 수 N이 주어진다.
둘째 줄에 각 자리의 상태 A_1, A_2, ..., A_N이 번호순으로 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 3 ≤ N ≤ 100,000, 0 ≤ A_i ≤ 9이다.

출력

선택한 구역의 시작 번호를 한 줄에 출력한다. 조건을 만족하는 후보 구역이 하나도 없으면 -1을 출력한다.

8
2 4 3 0 6 7 6 9

5

7
4 5 4 0 5 4 4

1

5
0 8 0 8 0

-1

출처: Devin.KR 자체 제작