레이팅 미적용The process of forming the Dutch government has taken more than half a year for three elections in a row. Perhaps we can streamline the initial stages of coalition building?
The first step after the election results is to find a group of parties (called a coalition) with enough seats to have a strict majority. Your task is to count the number of candidate coalitions that satisfy specific conditions. A coalition is considered a candidate coalition if it meets these two criteria:
- The total number of seats held by the coalition must be strictly more than half of the total seats across all parties.
- The coalition must be minimal in the sense that removing any one party from the coalition would cause it to lose its strict majority.
The input consists of:
- One line with an integer \(n\) (\(1 \le n \le 60\)), the number of parties.
- One line with \(n\) integers \(p\) (\(1 \le p \le 10\,000\)), the number of seats each party has.
Output the total number of candidate coalitions that satisfy the criteria above.
5
3 1 4 1 5
4
11
191 24 148 38 8 28 9 1 3 3 12
38
4
1 2 3 4
3