회의실의 추가 환기

문제

긴 복도를 따라 회의실 N개가 한 줄로 놓여 있다. 회의실에는 복도의 한쪽 끝부터 차례대로 1번부터 N번까지 번호가 붙어 있다. 관리자는 모든 회의실의 공기 상태를 같은 시각에 측정하고, 각 회의실에 대해 정수로 된 혼잡 지수를 기록했다. 혼잡 지수가 클수록 해당 회의실에 추가 환기가 더 필요한 것으로 본다. 이번 점검에서는 지수의 절댓값에 대한 기준을 정하지 않고, 바로 이웃한 회의실과의 비교만으로 추가 환기 대상을 고른다. 추가 환기 대상이 되려면 번호가 하나 작은 회의실과 번호가 하나 큰 회의실이 모두 존재해야 한다. 또한 자신의 혼잡 지수가 그 두 회의실의 혼잡 지수보다 각각 엄격하게 커야 한다. 예를 들어 어떤 회의실의 지수가 왼쪽 회의실보다 크더라도 오른쪽 회의실과 같으면 대상이 아니다. 두 이웃 중 하나라도 자신의 지수 이상이면 조건을 만족하지 않는다. 1번 회의실과 N번 회의실은 한쪽에 이웃이 없으므로 항상 추가 환기 대상에서 제외한다. 복도의 양 끝은 서로 이어져 있지 않다. 회의실 사이의 거리는 비교에 영향을 주지 않으며, 두 칸 이상 떨어진 회의실의 지수도 확인하지 않는다. 여러 회의실이 조건을 만족하면 그 회의실을 모두 선택한다. 서로 떨어진 회의실의 지수가 같더라도 각 회의실이 자신의 두 이웃보다 크다면 모두 선택될 수 있다. 선택 여부는 처음 측정한 지수만으로 한 번에 결정한다. 어떤 회의실을 대상으로 선택해도 그 회의실이나 이웃 회의실의 지수는 바뀌지 않는다. 선택한 회의실을 목록에서 제거하거나 남은 회의실끼리 새로 이웃하게 만드는 일도 없다. 관리자가 확인하기 쉽도록 조건을 만족하는 회의실 번호를 작은 순서대로 출력한다. 조건을 만족하는 회의실이 하나도 없다면 번호 목록 대신 0 하나를 출력한다.

입력

첫째 줄에 회의실 수를 나타내는 정수 N이 주어진다.
둘째 줄에 1번부터 N번 회의실까지의 혼잡 지수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
3 ≤ N ≤ 1,000
0 ≤ A_i ≤ 1,000
모든 혼잡 지수는 정수다.

출력

추가 환기 대상인 회의실 번호를 오름차순으로 한 줄에 공백으로 구분하여 출력한다. 대상이 없으면 0을 출력한다.

8
2 8 3 3 9 1 7 4

2 5 7

5
4 4 4 4 4

0

3
1 6 1

2

출처: Devin.KR 자체 제작