题目背景

CSP-J 2025 T4

题目描述

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

小 X 希望小 R 从这 n 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连拼成一个多边形。小 R 并不知道小木棍能拼成多边形的条件，于是小 X 直接将条件告诉了他：对于长度分别为 l1,l2,…,lm的 m 根小木棍，这 m 根小木棍能拼成一个多边形当且仅当 m≥3 且所有小木棍的长度之和大于所有小木棍的长度最大值的两倍，即。

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

输入格式

从文件polygon.in 中读入数据。 输入的第一行包含一个正整数n，表示小R的小木棍的数量。 输入的第二行包含n个正整数a1,a2,...,an，表示小 R 的小木棍的长度。

输出格式

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

输入输出样例

5
1 2 3 4 5

9

【样例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。

5
2 2 3 8 10

6

【样例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∼10的约束条件。 【样例4】 见选手目录下的polygon/polygon4.in 与 polygon/polygon4.ans。 该样例满足测试点11∼14的约束条件。

【子任务】 对于所有测试数据，保证： • 3≤n≤5,000； • 对于所有1≤i≤n，均有1≤ai≤5,000。