Background

こんな話など　忘れておくれ　/　Please forget stories like this.

言いたいことは　一つもないさ　/　There is not a single thing I want to say.

Problem Description

In a shop, there are $n$ "fishies" lined up in a row. The volume of the $i$-th "fishy" is $a_i$.

Yuki has a backpack with volume $V$. She plans to consider the "fishies" from $1$ to $n$ in order: if the current "fishy"'s volume is less than or equal to the remaining volume of the backpack, she puts this "fishy" into the backpack; otherwise, she does not. When a "fishy" with volume $x$ is put into the backpack, the remaining volume of the backpack decreases by $x$.

Since Yuki is a magical girl, she can choose the initial volume $\boldsymbol{V}$ of the backpack to be any non-negative integer, but she will not change the backpack's volume while considering the "fishies".

Let $s_i$ denote the selection status of the $i$-th "fishy". Specifically, if the $i$-th "fishy" is put into the backpack then $s_i=1$, otherwise $s_i=0$. You need to compute how many different sequences $s$ can be generated by the strategy above.

Input Format

The first line contains an integer $c$, indicating the subtask index of this test point. The samples satisfy $c=0$.

The second line contains an integer $n$.

The third line contains $n$ integers $a_1,\dots,a_n$.

Output Format

Output one line containing a non-negative integer, representing the number of different sequences $s$ that can be generated.

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

Hint

Sample 1 Explanation

• When the initial backpack volume $V=0$, $s=\{0,0,0\}$.
• When the initial backpack volume $V=2$, $s=\{1,0,0\}$.
• When the initial backpack volume $V=5$, $s=\{1,1,0\}$.
• When the initial backpack volume $V=23$, $s=\{1,1,1\}$.

It is easy to prove that when the initial backpack volume $V$ is any other non-negative integer, the generated $s$ must be one of these $4$ sequences, so the answer is $4$.

Sample 2 Explanation

• When the initial backpack volume $V=0$, $s=\{0,0,0,0\}$.
• When the initial backpack volume $V=1$, $s=\{1,0,0,0\}$.
• When the initial backpack volume $V=3$, $s=\{1,0,1,0\}$.
• When the initial backpack volume $V=4$, $s=\{1,1,0,0\}$.
• When the initial backpack volume $V=7$, $s=\{1,1,1,0\}$.
• When the initial backpack volume $V=10$, $s=\{1,1,1,1\}$.

It is easy to prove that when the initial backpack volume $V$ is any other non-negative integer, the generated $s$ must be one of these $6$ sequences, so the answer is $6$.

Constraints

For all testdata:

• $1 \le n \le 2\cdot10^5$.
• For all $1 \le i \le n$, $1 \le a_i \le 10^9$.

This problem uses bundled tests.

• Subtask 1 (7 points): $n \le 18$.
• Subtask 2 (11 points): $n \le 100$; for all $1 \le i \le n$, $a_i \le 100$.
• Subtask 3 (8 points): $n \le 500$; for all $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$; for all $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): the sequence $a$ is guaranteed to be non-increasing.
• Subtask 9 (17 points): no special constraints.

Translated by ChatGPT 5