题目描述

众所周知，宇宙中央大学是宇宙第一的大学，而宇宙中央大学软件学院又是宇宙中央大学最好的学院。

5205年，一年一度的奖学金评选活动在宇宙中央大学软件学院展开，参加奖学金答辩的同学会抽签决定答辩顺序。由于同学们个个身怀绝技，每个人在答辩的时候都会选用一个很特别的数字来展现自己的能力，来给在场的评委（以及其他同学）留下深刻印象！例如：

• 学分绩排名：1（在近十万名学生中排名第一）

• 参与科研项目数：8项（积极参与多项科研项目）

• 发表学术论文数量：114篇（在宇宙软件学报等顶刊上发表多篇论文）

• 获得奖项总数：24项（包括体育、艺术等多个领域）

• 开展各类宣讲19场，影响力超过19810人次。（深入社会实践，积累丰富经验）

• 志愿服务时长：114514小时（长期致力于志愿服务活动）

每位同学在答辩抽签之前决定他要展现的一个数字。假设一位同学展现了他的数字 a ，并且在他之前答辩的同学们展现的最大数是 b 。如果 2a ≤ b 或者 2b ≤ a ，评委和同学们都会感到很震撼。如果该同学之前无人答辩，则约定 b = 0。

我们想知道，在本场奖学金答辩的过程中，大家都一直保持震撼，我们就称这次是一次“可以震撼整个宇宙”的答辩。请你计算“可以震撼整个宇宙”的答辩顺序种数，结果对 998244353 取模。

输入格式

之后每组数据格式如下：

• 第一行包含一个整数 M ，表示答辩总人数。
• 第二行包含 M 个整数 z_1, z_2, ... , z_M ,表示每个人的数字。

输出格式

• 一个整数，结果对 998244353 取模。

示例

input

3
1 4 2

output

6

数据范围

• 对于 60% 的数据点，满足 1 ≤ M ≤ 5000
• 对于 100% 的数据点，满足 1 ≤ M ≤ 10^6
• 对于所有的 z_i , 1 ≤ z_i ≤ 10^9

限制

• 每个测试的时间限制：1s

• 每个测试的内存限制：512 MB