多边形（polygon）

题目描述

小 R 喜欢玩小木棍。小 R 有 n 根小木棍，第 i（1 ≤ i ≤ n）根小木棍的长度为 aᵢ。

小 X 希望小 R 从这 n 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连，拼成一个多边形。

小 R 并不知道小木棍能拼成多边形的条件，于是小 X 直接将条件告诉了他：

对于长度分别为 l₁, l₂, …, lₘ 的 m 根小木棍，这 m 根小木棍能拼成一个多边形，当且仅当：

• m ≥ 3；
• 所有小木棍的长度之和大于所有小木棍的长度最大值的两倍。

即：

l₁ + l₂ + … + lₘ > 2 × max(l₁, l₂, …, lₘ)

由于小 R 知道了小木棍能拼成多边形的条件，小 X 提出了一个更难的问题：有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形？

你需要帮助小 R 求出选出的小木棍能够拼成一个多边形的方案数。

两种方案不同，当且仅当选择的小木棍的下标集合不同，即存在 1 ≤ i ≤ n，使得其中一种方案选择了第 i 根小木棍，但另一种方案未选择。

由于答案可能较大，你只需要求出答案对 998244353 取模后的结果。

输入格式

从文件 polygon.in 中读入数据。

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

输入的第二行包含 n 个正整数 a₁, a₂, …, aₙ，表示小 R 的小木棍的长度。

输出格式

输出到文件 polygon.out 中。

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

样例 1

输入

5
1 2 3 4 5

输出

9

解释

共有以下 9 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：

样例 2

输入

5
2 2 3 8 10

输出

6

解释

共有以下 6 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：

样例 3

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

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

样例 4

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

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

子任务

对于所有测试数据，保证：

• 3 ≤ n ≤ 5000；
• 对于所有 1 ≤ i ≤ n，均有 1 ≤ aᵢ ≤ 5000。