题目描述

小 R 喜欢玩小木棍。小 R 有 n 根小木棍，第 i（1 <= i <= n）根小木棍的长度为 a_i。

小 X 希望小 R 从这 n 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连拼成一个多边形。对于长度分别为 l1, l2, ..., lm 的 m 根小木棍，这 m 根小木棍能拼成一个多边形当且仅当 m >= 3 且所有小木棍的长度之和大于所有小木棍的长度最大值的两倍，即 l1 + l2 + ... + lm > 2 x max(l1, ..., lm)。

小 X 提出了一个问题：有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形？你需要帮助小 R 求出选出的小木棍能够拼成一个多边形的方案数。两种方案不同当且仅当选择的小木棍的下标集合不同。由于答案可能较大，你只需要求出答案对 998244353 取模后的结果。

输入格式

输入的第一行包含一个正整数 n，表示小 R 的小木棍的数量。 输入的第二行包含 n 个正整数 a1, a2, ..., an，表示小 R 的小木棍的长度。

输出格式

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

样例 #1

输入：

5
1 2 3 4 5

输出：

9

样例 #2

输入：

5
2 2 3 8 10

输出：

6

提示

对于所有测试数据，保证：3 <= n <= 5000；对于所有 1 <= i <= n，均有 1 <= a_i <= 5000。

本题为 CSP-J 第二轮真题（2025 年，polygon）。

在线判题使用官方样例与补充测试数据，程序输出与答案一致即判对。