P4664 [BalticOI 2008] Elections (Day2)

The citizens of Byteland have recently been voting in the parliamentary elections. Now, when the results have been published, the parties have to decide on a coalition to form the government. Each party received a certain number of seats in the parliament. The coalition must be a subset of the parties such that together they have strictly more than half of all the seats in the parliament. It is desirable for the coalition to have as many seats as possible, to ensure they can still pass their proposed laws even if a few of their members are absent from a parliament session. A coalition is called redundant if one of its parties can be removed with the remaining ones still having more than half of the seats in the parliament. Of course, such a removable party would effectively have no power — the other members of the coalition would be able to force the laws regardless of its opinion. #### Task Write a program that: - reads the election results from the standard input, - finds a non-redundant coalition that has the maximal possible number of seats in the parliament, - writes the description of this coalition to the standard output.

The first line of the standard input contains one integer $n\ (1\le n\le 300)$ — the number of parties that participated in the elections. The parties are numbered from $1$ to $n$. The second line contains n nonnegative integers $a_1,\dots,a_n$, separated by single spaces, where $a_i$ is the number of seats received by the $i$-th party. You may assume that the total number of seats in the parliament will be positive and lower or equal to $100000$. Additionally, in test cases worth $40\%$ of points, the number of parties will not exceed $20$.

The first line of the standard output should contain one integer $k$ — the number of parties in a non-redundant coalition which has the maximal number of seats. The second line should contain $k$ distinct integers separated by single spaces — the numbers of parties that form the coalition. If there are several non-redundant coalitions with the maximal number of seats, you may output any of them. The member parties can be listed in any order.

Resource: Baltic Olympiad in Informatics 2008.