Maximal Non‐Redundant Coalition

The citizens of Byteland have recently cast their votes in the parliamentary elections. After the results have been published, political parties now need to form a coalition in the parliament in order to govern.

There are n parties (numbered from 1 to n). The i-th party received a_i seats in the parliament. A coalition is defined as a subset of these parties such that the total number of seats in the coalition, \( S \), is strictly greater than half of all seats in parliament, i.e., \[ S > \frac{T}{2}, \] where \( T = \sum_{i=1}^{n} a_i \) is the total number of seats.

Moreover, a coalition is considered non‐redundant if no party can be removed without losing the majority. In other words, for every party \( j \) in the coalition with a_j seats, if we remove that party then the remaining seats satisfy \[ S - a_j \le \frac{T}{2}. \] Thus, equivalently, if we denote \( m \) as the minimum number of seats among all parties in the coalition, then we must have \[ S \le \frac{T}{2} + m. \]

Your task is to find a coalition that is non‐redundant and has the maximal possible number of seats. If there are several such coalitions, any one of them is acceptable.

Problem Summary

• Total seats \( T = \sum_{i=1}^{n} a_i \).
• A coalition (subset of parties) must have \( S > \frac{T}{2} \).
• It must be non‐redundant: for every party in the coalition, \( S - a_i \le \frac{T}{2} \), or equivalently, if \( m \) is the minimum seats in the coalition then \( S \le \frac{T}{2} + m \).
• You need to maximize \( S \) (the coalition's total seats) under these restrictions.

inputFormat

The first line contains a single integer \( n \) (\(1 \le n \le 300\)) — the number of parties.

The second line contains \( n \) nonnegative integers \( a_1, a_2, \dots, a_n \) separated by spaces, where \( a_i \) is the number of seats received by the \( i \)-th party. You may assume that \( T = \sum_{i=1}^{n} a_i \) is positive and \( T \le 100000 \). In some test cases (worth 40% of the points) \( n \) will not exceed 20.

outputFormat

The first line should contain a single integer \( k \) — the number of parties in the chosen coalition.

The second line should contain \( k \) distinct integers separated by spaces — the indices of the parties forming the coalition. The order of indices does not matter.

sample

3
4 3 1

2
1 2