题目描述

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

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

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

输入格式

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

输入的第二行包含n个正整数a_1,a_2,....,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。

共有以下 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

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

样例 4

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

子任务

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

• 3 ≤ n ≤ 5, 000；

• 对于所有 1 ≤ i ≤ n，均有 1 ≤ a_i≤ 5, 000。

样例

输入样例 1

5
1 2 3 4 5

输出样例 1

9

输入样例 2

5
2 2 3 8 10

输出样例 2

6