说明

商店里有 $n$ 条「鱼鱼」排成一排，第 $i$ 条「鱼鱼」的体积为 $a_i$。

Yuki 有一个体积为 $V$ 的背包，她打算从 $1$ 到 $n$ 依次考虑每条「鱼鱼」：如果当前「鱼鱼」的体积小于等于背包剩余体积，则将该「鱼鱼」装入背包，否则不将该「鱼鱼」装入背包。当一条体积为 $x$ 的「鱼鱼」被装入背包时，背包的剩余体积会减少 $x$。

由于 Yuki 是魔法少女，她可以让背包的 初始体积 $\boldsymbol{V}$ 为任意非负整数，不过她不会在考虑「鱼鱼」的过程中修改背包的体积。

设 $s_i$ 表示第 $i$ 条「鱼鱼」的选取状态；具体地，若第 $i$ 条「鱼鱼」被装入背包了则 $s_i=1$，否则 $s_i=0$。你需要求出，上述策略可以生成多少种序列 $s$。

输入格式

第一行包含一个整数 $c$，表示该测试点所属的子任务编号。样例满足 $c=0$。

第二行包含一个整数 $n$。

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

输出格式

输出一行，包含一个非负整数，表示可以生成的不同的序列 $s$ 的数量。

0
3
1 3 8

4

0
4
1 3 1 4

6

0
5
16 8 4 2 1

32

0
6
7 4 4 6 8 7

9

提示

样例 1 解释

• 当背包的初始体积 $V=0$ 时，$s=\{0,0,0\}$；
• 当背包的初始体积 $V=2$ 时，$s=\{1,0,0\}$；
• 当背包的初始体积 $V=5$ 时，$s=\{1,1,0\}$；
• 当背包的初始体积 $V=23$ 时，$s=\{1,1,1\}$。

容易证明，当背包的初始体积 $V$ 等于其他非负整数时，生成的 $s$ 一定为这 $4$ 种中的 $1$ 种，因此答案为 $4$。

样例 2 解释

• 当背包的初始体积 $V=0$ 时，$s=\{0,0,0,0\}$；
• 当背包的初始体积 $V=1$ 时，$s=\{1,0,0,0\}$；
• 当背包的初始体积 $V=3$ 时，$s=\{1,0,1,0\}$；
• 当背包的初始体积 $V=4$ 时，$s=\{1,1,0,0\}$；
• 当背包的初始体积 $V=7$ 时，$s=\{1,1,1,0\}$；
• 当背包的初始体积 $V=10$ 时，$s=\{1,1,1,1\}$；

容易证明，当背包的初始体积 $V$ 等于其他非负整数时，生成的 $s$ 一定为这 $6$ 种中的 $1$ 种，因此答案为 $6$。

数据范围

对于所有测试数据，均有：

• $1 \le n \le 2\cdot10^5$；
• 对于所有 $1 \le i \le n$，均有 $1 \le a_i \le 10^9$。

本题采用捆绑测试。

• Subtask 1（7 points）：$n \le 18$。
• Subtask 2（11 points）：$n \le 100$；对于所有 $1 \le i \le n$，均有 $a_i \le 100$。
• Subtask 3（8 points）：$n \le 500$；对于所有 $1 \le i \le n$，均有 $a_i \le 500$。
• Subtask 4（5 points）：$n \le 500$。
• Subtask 5（12 points）：$n \le 8\cdot10^3$；对于所有 $1\le i \le n$，均有 $a_i \le 8\cdot10^3$；
• Subtask 6（15 points）：$n \le 8\cdot10^3$。
• Subtask 7（13 points）：$n \le 8\cdot 10^4$。
• Subtask 8（12 points）：保证序列 $a$ 单调不增。
• Subtask 9（17 points）：无特殊限制。