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

小 X 希望小 R 从这 n 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连拼成一个多边形。小 R 并不知道小木棍能拼成多边形的条件，于是小 X 直接将条件告诉了他：

对于长度分别为 l_1, l_2, \dots , l_m 的 m 根小木棍，这 m 根小木棍能拼成一个多边形当且仅当 m \ge 3 且所有小木棍的长度之和大于所有小木棍的长度最大值的两倍，即

\sum_{i=1}^{m} l_i > 2 \times \max_{i=1}^{m} l_i 。

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

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

输入的第二行包含 n 个正整数 a_1, a_2, \dots , a_n，表示小 R 的小木棍的长度。

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

【样例 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 \le n \le 5, 000；
• 对于所有 1 \le i \le n，均有 1 \le a_i \le 5, 000。

CSP-J/S 2025 第二轮认证

CSP-J