지하철 대기 구역 점검

문제

한 지하철 승강장에는 대기 구역 N개가 일렬로 놓여 있다. 구역 번호는 승강장의 한쪽 끝에서부터 1번, 2번, …, N번이다. 운영 담당자는 같은 시각에 각 구역에서 기다리는 사람 수를 조사하여 번호 순서대로 배열에 기록했다. 이 자료를 이용해 양옆보다 사람이 많은 구역을 찾아 안내 표지의 위치를 점검하려 한다. 점검 대상은 바로 왼쪽 구역과 바로 오른쪽 구역이 모두 존재하는 구역 중에서 정한다. 어떤 구역의 대기 인원이 바로 왼쪽 구역의 대기 인원보다 많고, 동시에 바로 오른쪽 구역의 대기 인원보다 많으면 그 구역을 점검 대상으로 선택한다. 여기서 많다는 것은 두 수가 같지 않고 앞의 수가 더 크다는 뜻이다. 한쪽 이웃과라도 인원이 같으면 선택하지 않는다. 1번 구역과 N번 구역은 양옆 구역을 모두 갖고 있지 않으므로 대기 인원이 아무리 많아도 점검 대상이 아니다. N이 1 또는 2이면 이러한 조건을 검사할 구역 자체가 없다. 또한 승강장 전체에서 가장 많은 사람이 모인 구역만 찾는 것이 아니다. 전체 최댓값보다 작은 인원이라도 자신의 바로 양옆보다 많으면 선택한다. 조사된 인원은 모두 한 시각의 값이다. 어떤 구역을 점검 대상으로 선택하더라도 사람을 이동시키거나 배열의 값을 바꾸지 않는다. 따라서 모든 구역의 선택 여부는 처음 주어진 자료만으로 독립적으로 판단한다. 선택된 구역이 여러 개이면 구역 번호가 작은 순서대로 보고한다. 조건에 맞는 구역이 하나도 없으면 별도로 정해진 값 0을 보고한다. 대기 인원 배열이 주어졌을 때 보고할 구역 번호를 구하는 프로그램을 작성한다.

입력

첫째 줄에 구역 수를 나타내는 정수 N이 주어진다. 1≤N≤1,000이다.
둘째 줄에 각 구역의 대기 인원 A1, A2, …, AN이 번호 순서대로 공백으로 구분되어 주어진다. 각 Ai는 정수이며 0≤Ai≤1,000이다.

출력

점검 대상으로 선택된 구역 번호를 오름차순으로 한 줄에 공백으로 구분하여 출력한다. 선택된 구역이 없으면 0만 출력한다.

8
4 9 3 6 6 2 5 1

2 7

5
2 4 4 3 1

0

1
1000

0

출처: Devin.KR 자체 제작