Description

荷兰政府的组建过程在连续三次选举中都花费了半年以上的时间。或许我们可以简化联合组阁的初始阶段？

选举结果公布后的第一步，是找到一个拥有足够席位的党派组合（称为“联盟”），使其拥有严格多数席位。 你的任务是统计满足特定条件的候选联盟的数量。 一个联盟被认为是“候选联盟”，当且仅当满足以下两个条件：

严格多数： 该联盟所拥有的席位总数必须严格大于所有党派席位总数的一半。

无多余党派： 该联盟必须是极小的，即移除联盟中的任意一个党派后，联盟将失去严格多数。

:::align{center}

图 D.1：样例输入 2 的示意图。

:::

Input Format

输入包括：

• 一行一个整数 $n$（$1 \le n \le 60$），表示党派数量。
• 一行 $n$ 个整数 $p$（$1 \le p \le 10\,000$），表示每个党派拥有的席位数。

Output Format

输出满足上述条件的候选联盟的总数。

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

Hint

由 ChatGPT 4.1 翻译