P15870 [MX-X26-T6] "Cfz Round 7" vivi

こんな話など　忘れておくれ　/　Please forget stories like this. 言いたいことは　一つもないさ　/　There is not a single thing I want to say.

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.

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 one line containing a non-negative integer, representing the number of different sequences $s$ that can be generated.

### 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