有 $n$ 根木棍，第 $i$ 根木棍的长度为 $a_i$。选择一个下标集合 $I\subseteq\{1,2,\dots,n\}$ 后，当且仅当

$$|I|\geq 3\quad\text{且}\quad\sum_{i\in I}a_i>2\max_{i\in I}a_i$$

时，这些木棍可以构成一个多边形。

求满足条件的下标集合数量，并对 $998244353$ 取模。即使两根木棍长度相同，只要下标不同，仍视为不同的木棍。

输入格式

第一行一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

输出满足条件的方案数对 $998244353$ 取模后的结果。

样例 1

5
1 2 3 4 5

9

样例 2

5
2 2 3 8 10

6

数据范围与原题特殊限制

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

• $3 \leq n \leq 5\,000$;
• 对于所有 $1 \leq i \leq n$，均有 $1 \leq a_i \leq 5\,000$。

测试点编号	$n \leq$	$\max_{i=1}^{n} a_i \leq$
$1 \sim 3$	$3$	$10$
$4 \sim 6$	$10$	$10^2$
$7 \sim 10$	$20$
$11 \sim 14$	$500$
$15 \sim 17$		$1$
$18 \sim 20$	$5\,000$
$21 \sim 25$		$5\,000$

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。