5993.T4-[CSP-J 2025] 多边形polygon

## 题目描述

小 R 喜欢玩小木棍。小 R 有 $n$ 根小木棍，第 $i$ ($1 \leq i \leq n$) 根小木棍的长度为 $a_i$。

小 X 希望小 R 从这 $n$ 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连拼成一个多边形。小 R 并不知道小木棍能拼成多边形的条件，于是小 X 直接将条件告诉了他：对于长度分别为 $l\_1, l\_2, \dots, l\_m$ 的 $m$ 根小木棍，这 $m$ 根小木棍能拼成一个多边形当且仅当 $m \geq 3$ 且所有小木棍的长度之和**大于**所有小木棍的长度最大值的两倍，即 $\sum\_{i=1}^{m} l\_i > 2 \times \max\_{i=1}^{m} l_i$。

由于小 R 知道了小木棍能拼成多边形的条件，小 X 提出了一个更难的问题：有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形？你需要帮助小 R 求出选出的小木棍能够拼成一个多边形的方案数。两种方案不同当且仅当选择的小木棍的**下标集合不同**，即存在 $1 \leq i \leq n$，使得其中一种方案选择了第 $i$ 根小木棍，但另一种方案未选择。由于答案可能较大，你只需要求出答案对 $998,244,353$ 取模后的结果。

## 输入格式

输入的第一行包含一个正整数 $n$，表示小 R 的小木棍的数量。

输入的第二行包含 $n$ 个正整数 $a\_1, a\_2, \dots, a\_n$，表示小 R 的小木棍的长度。

## 输出格式

输出一行一个非负整数，表示小 R 选出的小木棍能够拼成一个多边形的方案数对 $998,244,353$ 取模后的结果。

## 输入输出样例 #1

### 输入 #1

```
5
1 2 3 4 5
```

### 输出 #1

```
9
```

## 输入输出样例 #2

### 输入 #2

```
5
2 2 3 8 10
```

### 输出 #2

```
6
```

## 说明/提示

### 【样例 1 解释】

共有以下 $9$ 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：
1. 选择第 $2, 3, 4$ 根小木棍，长度之和为 $2 + 3 + 4 = 9$，长度最大值为 $4$;
2. 选择第 $2, 4, 5$ 根小木棍，长度之和为 $2 + 4 + 5 = 11$，长度最大值为 $5$;
3. 选择第 $3, 4, 5$ 根小木棍，长度之和为 $3 + 4 + 5 = 12$，长度最大值为 $5$;
4. 选择第 $1, 2, 3, 4$ 根小木棍，长度之和为 $1 + 2 + 3 + 4 = 10$，长度最大值为 $4$;
5. 选择第 $1, 2, 3, 5$ 根小木棍，长度之和为 $1 + 2 + 3 + 5 = 11$，长度最大值为 $5$;
6. 选择第 $1, 2, 4, 5$ 根小木棍，长度之和为 $1 + 2 + 4 + 5 = 12$，长度最大值为 $5$;
7. 选择第 $1, 3, 4, 5$ 根小木棍，长度之和为 $1 + 3 + 4 + 5 = 13$，长度最大值为 $5$;
8. 选择第 $2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 4 + 5 = 14$，长度最大值为 $5$;
9. 选择第 $1, 2, 3, 4, 5$ 根小木棍，长度之和为 $1 + 2 + 3 + 4 + 5 = 15$，长度最大值为 $5$。

### 【样例 2 解释】

共有以下 $6$ 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：
1. 选择第 $1, 2, 3$ 根小木棍，长度之和为 $2 + 2 + 3 = 7$，长度最大值为 $3$;
2. 选择第 $3, 4, 5$ 根小木棍，长度之和为 $3 + 8 + 10 = 21$，长度最大值为 $10$;
3. 选择第 $1, 2, 4, 5$ 根小木棍，长度之和为 $2 + 2 + 8 + 10 = 22$，长度最大值为 $10$;
4. 选择第 $1, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 8 + 10 = 23$，长度最大值为 $10$;
5. 选择第 $2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 8 + 10 = 23$，长度最大值为 $10$;
6. 选择第 $1, 2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 2 + 3 + 8 + 10 = 25$，长度最大值为 $10$。

### 【样例 3】

见选手目录下的 $polygon/polygon3.in$ 与 $polygon/polygon3.ans$。

该样例满足测试点 $7 \sim 10$ 的约束条件。

### 【样例 4】

见选手目录下的 $polygon/polygon4.in$ 与 $polygon/polygon4.ans$。

该样例满足测试点 $11 \sim 14$ 的约束条件。

### 【子任务】

对于所有测试数据，保证：
- $3 \leq n \leq 5,000$;
- 对于所有 $1 \leq i \leq n$，均有 $1 \leq a_i \leq 5\,000$。

| 测试点编号 | $n \leq$ | $\max_{i=1}^{n} a_i \leq$ |
| :--: | :--: | :--: |
| $1 \sim 3$ | $3$ | $10$ |
| $4 \sim 6$ | $10$ | $10^2$|
| $7 \sim 10$ | $20$ | $10^2$ |
| $11 \sim 14$ | $500$ | $10^2$ |
| $15 \sim 17$ | $500$ | $1$ |
| $18 \sim 20$ | $5\,000$ | $1$ |
| $21 \sim 25$ | $5\,000$ | $5\,000$ |