Description
Description
Extinction is a complex card game involving betting. In the final phase of the game, each round players must bet the amount of money that the poorest player has remaining. When someone is out of money, they drop out of the game. Play continues until only one player remains.
Dr. Xenovian plays in an Extinction tournament. Assuming she starts the final phase of the game with the most money and wins every round, can you track how many of her opponents will remain each round?
Suppose Dr. Xenovian has six opponents with the following amounts of money left (in thousands of dollars):
5 4 4 2 2 8
Then, in the first round, should would bet $2,000, which will bankrupt two of the players. For the next round, four opponents are left with the following amounts of money:
3 2 2 _ _ 6
The above step is repeated until no opponents are left.
Input Format
The first line contains a single integer N indicating the number of opponents.
The next line contains N integers: a0 , a1 , …, aN-1 separated by spaces, where a represents the amount of money that the i th player has.
Constraints
1 ≤ N ≤ 1000
1 ≤ ai ≤ 1000
Output Format
For each pass, print the number of opponents that remain.
Example 0
Sample Input
6
5 4 4 2 2 8
Sample Output
6
4
2
1
Explanation
In the first round, there are six opponents (provided in the input file).
Dr. Xenovian bets 2, driving out two of the opponents and leaving the four others with 3 2 2 and 6 respectively.
Dr. Xenovian bets 2 again, driving out two more opponents. The last two have 1 and 4 left.
Round three, the bet is 1, cutting down to one opponent with 3 left.
Finally the last opponent is eliminated and the game ends (no need to output 0).
Example 1
Sample Input
8
1 2 3 4 3 3 2 1
Sample Output
8
6
4
1
Example 2
Sample Input
8
8 8 14 10 3 5 14 12
Sample Output
8
7
6
4
3
2
