Best Solution Unknown

시간 제한3초메모리 제한512 MB

요약

인접한 두 선수가 겨루어 강한 쪽이 이기고 승자의 힘이 1 늘어나는 대회에서, 우승할 수 있는 모든 선수의 번호를 구합니다.

난이도: 어려움10점 중 8점
유형: 스택, 그리디, 이분 탐색
정답자: 아직 제출이 없습니다

문제

당신은 Best Solution Unknown (BSU) 대회의 책임자입니다. 이 대회의 규칙은 단순하지만 다소 특이합니다.

먼저 참가자 $n$ 명이 한 줄로 섭니다. 이후 $n-1$ 번의 경기가 열립니다. 각 경기에서 심사위원은 인접한 두 참가자를 고릅니다. 선택된 두 참가자에게는 NP-hard 문제가 주어지고, 두 사람은 최선을 다해 좋은 해를 찾습니다. 더 나은 해를 낸 쪽이 경기에서 이기고, 다른 쪽은 대회에서 탈락합니다. 그 뒤 참가자들이 다시 줄을 맞추어, 탈락한 참가자의 옆 사람이 승자와 이웃하게 됩니다. $n-1$ 번의 경기가 모두 끝나면 한 명만 남고, 그 사람이 대회 우승자로 선언됩니다.

왼쪽에서부터 $i$ 번째 참가자의 실력은 $a_i$ 입니다. 대회 전에 모든 참가자의 실력을 알고 있습니다. 실력이 더 높은 참가자가 경기에서 이깁니다. 실력이 같으면 어느 쪽이든 이길 수 있습니다. 경기에서 이긴 참가자의 실력은 1 증가합니다.

누가 어떤 경기에 나서는지, 실력이 같을 때 누가 이기는지는 알 수 없습니다. 우승자가 될 수 있는 참가자를 모두 구하세요.

입력

첫째 줄에 참가자 수 $n$ ( $1 \le n \le 10^6$ )이 주어집니다. 둘째 줄에는 $i$ 번째 참가자의 초기 실력 $a_i$ ( $1 \le a_i \le 10^9$ ) $n$ 개가 주어집니다.

출력

첫째 줄에 우승자가 될 수 있는 참가자의 수 $k$ ( $1 \le k \le n$ )를 출력합니다. 둘째 줄에는 그 참가자들의 번호 $b_i$ 를 증가하는 순서로 $k$ 개 출력합니다 ( $1 \le b_1 < b_2 < \ldots < b_k \le n$ ).

예제4

예제 1
입력
```
3
3 2 2
```
예상 출력
```
3
1 2 3
```
예제 2
입력
```
3
1 2 1
```
예상 출력
```
1
2
```
예제 3
입력
```
5
1 2 3 5 5
```
예상 출력
```
3
3 4 5
```
예제 4
입력
```
1
10
```
예상 출력
```
1
1
```