311243: CF1955C. Inhabitant of the Deep Sea

C. Inhabitant of the Deep Seatime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

$n$ ships set out to explore the depths of the ocean. The ships are numbered from $1$ to $n$ and follow each other in ascending order; the $i$-th ship has a durability of $a_i$.

The Kraken attacked the ships $k$ times in a specific order. First, it attacks the first of the ships, then the last, then the first again, and so on.

Each attack by the Kraken reduces the durability of the ship by $1$. When the durability of the ship drops to $0$, it sinks and is no longer subjected to attacks (thus the ship ceases to be the first or last, and the Kraken only attacks the ships that have not yet sunk). If all the ships have sunk, the Kraken has nothing to attack and it swims away.

For example, if $n=4$, $k=5$, and $a=[1, 2, 4, 3]$, the following will happen:

1. The Kraken attacks the first ship, its durability becomes zero and now $a = [2, 4, 3]$;
2. The Kraken attacks the last ship, now $a = [2, 4, 2]$;
3. The Kraken attacks the first ship, now $a = [1, 4, 2]$;
4. The Kraken attacks the last ship, now $a = [1, 4, 1]$;
5. The Kraken attacks the first ship, its durability becomes zero and now $a = [4, 1]$.

How many ships were sunk after the Kraken's attack?

Input

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le 10^{15}$) — the number of ships and how many times the Kraken will attack the ships.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the durability of the ships.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output the number of ships sunk by the Kraken on a separate line.

ExampleInput

6
4 5
1 2 4 3
4 6
1 2 4 3
5 20
2 7 1 8 2
2 2
3 2
2 15
1 5
2 7
5 2

Output

2
3
5
0
2
2

题目大意：
C.深海居民
有n艘船出海探险，它们的编号从1到n，并且按照升序排列；第i艘船的耐久度为a_i。
一只克拉肯（Kraken）以特定的顺序攻击了这些船k次。首先攻击第一艘船，然后是最后一艘，然后再次攻击第一艘，以此类推。
每次克拉肯的攻击都会使船的耐久度减少1。当船的耐久度降到0时，船会沉没并且不再受到攻击（因此船不再是第一艘或最后一艘，克拉肯只攻击那些尚未沉没的船）。如果所有的船都沉没了，克拉肯就没有东西可以攻击，然后它会游走。
输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例的第一行包含两个整数n和k（1≤n≤2×10^5，1≤k≤10^15）——船的数量和克拉肯将攻击船的次数。
每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^9）——船的耐久度。
保证所有测试用例的n之和不超过2×10^5。
输出：
对于每个测试用例，输出克拉肯击沉的船的数量。题目大意： C.深海居民 有n艘船出海探险，它们的编号从1到n，并且按照升序排列；第i艘船的耐久度为a_i。 一只克拉肯（Kraken）以特定的顺序攻击了这些船k次。首先攻击第一艘船，然后是最后一艘，然后再次攻击第一艘，以此类推。 每次克拉肯的攻击都会使船的耐久度减少1。当船的耐久度降到0时，船会沉没并且不再受到攻击（因此船不再是第一艘或最后一艘，克拉肯只攻击那些尚未沉没的船）。如果所有的船都沉没了，克拉肯就没有东西可以攻击，然后它会游走。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含两个整数n和k（1≤n≤2×10^5，1≤k≤10^15）——船的数量和克拉肯将攻击船的次数。 每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^9）——船的耐久度。 保证所有测试用例的n之和不超过2×10^5。 输出： 对于每个测试用例，输出克拉肯击沉的船的数量。