창고 선반의 돌출 상자

문제

물류 창고의 긴 선반에는 상자 N개가 왼쪽에서 오른쪽으로 한 줄로 놓여 있다. 직원은 선반 앞을 지나가는 운반 장치가 상자에 걸리지 않도록, 주변보다 높이 솟은 상자의 위치를 확인하려고 한다. 상자는 왼쪽부터 차례대로 1번부터 N번까지 번호가 붙어 있고, 각 상자의 높이는 같은 단위의 양의 정수로 기록되어 있다. 직원은 바로 이웃한 상자만 비교하여 돌출 상자를 정한다. 어떤 상자의 높이가 왼쪽에 바로 붙어 있는 상자보다 엄격히 높고, 동시에 오른쪽에 바로 붙어 있는 상자보다 엄격히 높으면 그 상자를 돌출 상자라고 한다. 더 멀리 떨어진 상자의 높이는 이 판단에 영향을 주지 않는다. 선반의 양 끝도 같은 방식으로 비교할 수 있도록, 1번 상자의 왼쪽과 N번 상자의 오른쪽에는 높이가 0인 빈 공간이 있다고 생각한다. 빈 공간에는 상자 번호를 붙이지 않으며 결과에도 포함하지 않는다. 따라서 첫 번째 상자는 오른쪽 상자보다 높으면 돌출 상자가 될 수 있고, 마지막 상자는 왼쪽 상자보다 높으면 돌출 상자가 될 수 있다. 상자가 하나뿐이면 그 상자의 양옆을 모두 높이 0인 빈 공간으로 비교한다. 높이가 같은 것은 더 높은 것으로 인정하지 않는다. 특히 같은 높이의 상자가 나란히 놓여 있으면, 그 두 상자는 서로를 이웃으로 가지므로 어느 쪽도 돌출 상자가 될 수 없다. 모든 판정은 처음 주어진 상자 배치를 기준으로 수행한다. 돌출 상자를 찾았다고 해서 상자를 치우거나 높이를 바꾸지 않는다. 직원이 표시해야 할 돌출 상자의 개수와 번호를 구한다. 번호는 선반을 살펴보는 방향에 맞추어 작은 번호부터 출력한다. 돌출 상자가 하나도 없는 배치도 주어질 수 있으며, 이때는 개수 0만 출력한다.

입력

첫째 줄에 상자의 개수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 1,000이다.
둘째 줄에 왼쪽부터 차례대로 상자의 높이를 나타내는 N개의 정수 H가 공백으로 구분되어 주어진다. 각 높이는 1 이상 1,000 이하이다.

출력

첫째 줄에 돌출 상자의 개수 K를 출력한다. K가 양수이면 둘째 줄에 돌출 상자의 번호 K개를 오름차순으로 공백으로 구분하여 출력한다. K가 0이면 첫째 줄에 0만 출력한다.

7
4 2 5 5 1 3 2

2
1 6

4
8 8 8 8

0

1
1

1
1

출처: Devin.KR 자체 제작