407986: GYM102956 N Best Solution Unknown

Memory Limit:0 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

N. Best Solution Unknowntime limit per test3 secondsmemory limit per test512 mebibytesinputstandard inputoutputstandard output

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.

Input

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$$$).

Output

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$$$).

ExamplesInput
3
3 2 2
Output
3
1 2 3 
Input
3
1 2 1
Output
1
2 
Input
5
1 2 3 5 5
Output
3
3 4 5 
Input
1
10
Output
1
1 

加入题单

上一题 下一题 算法标签: