Inhabitant of the Deep Sea
Contest: Codeforces Round 938 (Div. 3)
Difficulty rating: 1300
Tags: greedy, implementation, math

$$$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 format:
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 format:
For each test case, output the number of ships sunk by the Kraken on a separate line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
2
3
5
0
2
2

Editorial:
To solve the problem, let's model the behavior of the Kraken. Suppose initially there are two or more ships in the sea, we will consider the first and last ship, denote their durabilities as $$$a_l$$$ and $$$a_r$$$, and also let $$$m = \min(a_l, a_r)$$$, initially setting $$$l = 1$$$ and $$$r = n$$$.
After two attacks, the durability of both ships will decrease by $$$1$$$. If $$$k \ge 2 \cdot m$$$, then we need to subtract $$$m$$$ from the durabilities of both ships, and also reduce the remaining attacks of the Kraken by $$$2 \cdot m$$$. If $$$k < 2 \cdot m$$$, then the Kraken will inflict $$$\lfloor {k \over 2} \rfloor$$$ damage to the $$$r$$$-th ship. In this case, if $$$k$$$ is odd, the $$$l$$$-th ship will receive $$$\lfloor {k \over 2} \rfloor + 1$$$ damage, otherwise $$$\lfloor {k \over 2} \rfloor$$$ damage.
After these attacks, some ships may have sunk. If $$$a_l = 0$$$, we increase $$$l$$$ by $$$1$$$, if $$$a_r = 0$$$, we decrease $$$r$$$ by $$$1$$$, and move on to considering the next pair of ships that will be under attack by the Kraken. If at some point $$$l = r$$$, it means that there is only one ship left in the sea, and the Kraken can sink it if $$$k \ge a_l$$$.
A deque is perfect for this problem, allowing us to not think about $$$l$$$ and $$$r$$$ and simply look at the first and last elements in the queue. At each step of considering a pair of ships, either the Kraken's attacks end, or at least one ship sinks. The final complexity of the solution is $$$O(n)$$$.