$$$n$$$ 渔民刚刚结束钓鱼假期。第 $$$i$$$ 渔夫捕获了一条重量为 $$$a_i$$$ 的鱼。
渔民们要互相炫耀他们捕获的鱼。为此,他们首先选择展示鱼的顺序(每个渔夫只展示一次他的鱼,因此,形式上,展示鱼的顺序是从 $$$1$$$ 到 $$$n$$$ 的整数排列)。然后他们按照选择的顺序展示他们捕获的鱼。当渔夫展示他的鱼时,他可能会变得高兴,变得悲伤,或者保持满足。
假设渔夫展示了一条重量为 $$$x$$$ 的鱼,之前展示的鱼的最大重量为 $$$y$$$(如果该渔夫是第一个展示他的鱼,则$$$y = 0$$$)。然后:
- 如果$$$x \ge 2y$$$,渔夫变得快乐;
- 如果$$$2x \le y$$$,渔夫会变得悲伤;
- 如果这两个条件都不满足,渔夫就会满意。
如果在所有渔民都按照这个顺序展示他们的鱼之后,每个渔民变得快乐或悲伤,我们就称之为渔民展示他们的鱼情绪化的顺序。计算情感订单数以 $$$998244353$$$ 为模。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5000$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
输出
打印一个整数 — 情感订单的数量,以 $$$998244353$$$ 为模。
示例
输入 #1
4 1 1 4 9
输出 #1
20
输入 #2
4 4 3 2 1
输出 #2
0
输入 #3
3 4 2 1
输出 #3
6
输入#4
8 42 1337 13 37 420 666 616 97
输出#4
19200