시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 73 | 38 | 31 | 54.386% |
You are the responsible holder of a competition called Best Solution Unknown (BSU). The rules of this competition are simple but rather quirky.
First, all the $n$ participants stand in a row. Then, $n-1$ matches are held. In each match, jury chooses two adjacent players. The chosen players are given an NP-hard problem, and they try their best to come up with a good solution. The one who provides a better solution wins a round, the other one leaves the competition. After that, players shift to form a valid row again, so the player adjacent to the player that has left the competition becomes adjacent to the winner of the round. As you can see, after all the $n-1$ matches, only one player remains, and this player is declared a winner of the competition.
You know the competitors well, so you know the strength of each player before the competition. The strength of the $i$-th player, counting from the left of the row, is $a_i$. You also know that a player with greater strength wins the match. If the players have equal strength, both have a chance to win. You have noticed that victories motivate the players, so the strength of the winner of a match increases by one.
However, you do not know who plays in each match and who wins a match in case of equal strengths. So, you are wondering who can become the winner of the competition. You thought it was a good problem for the participants of BSU, but, unfortunately, it is not NP-hard, so you have to solve it yourself.
The first line contains an integer $n$, denoting the number of participants of BSU ($1 \le n \le 10^6$).
The second line contains $n$ integers $a_i$, where $a_i$ is the initial strength of the $i$-th participant ($1 \le a_i \le 10^9$).
The first line should contain an integer $k$, the number of participants that can possibly win the competition ($1 \le k \le n$).
The second line should contain $k$ integers $b_i$ in strictly increasing order, the indices of these participants ($1 \le b_1 < b_2 < \ldots < b_k \le n$).
3 3 2 2
3 1 2 3
3 1 2 1
1 2
5 1 2 3 5 5
3 3 4 5
1 10
1 1