Dutch Democracy

문제

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:

Strict Majority: The total number of seats held by the coalition must be strictly more than half of the total seats across all parties.

No Superfluous 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.

Figure D.1: Illustration of Sample Input 2.

입력

The input consists of:

• One line with an integer $nn$ ($1\le n\le 601\; \backslash le\; n\; \backslash le\; 60$), the number of parties.
• One line with $nn$ integers $pp$ ($1\le p\le 100001\; \backslash le\; p\; \backslash le\; 10\backslash ,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