311167: CF1943E2. MEX Game 2 (Hard Version)

This is the hard version of the problem. The only difference between the two versions is the constraint on $t$, $m$ and the sum of $m$. You can make hacks only if both versions of the problem are solved.

Alice and Bob play yet another game on an array $a$ of size $n$. Alice starts with an empty array $c$. Both players take turns playing, with Alice starting first.

On Alice's turn, she picks one element from $a$, appends that element to $c$, and then deletes it from $a$.

On Bob's turn, he picks at most $k$ elements from $a$, and then deletes it from $a$.

The game ends when the array $a$ is empty. Alice's score is defined to be the MEX$^\dagger$ of $c$. Alice wants to maximize her score while Bob wants to minimize it. Find Alice's final score if both players play optimally.

The array will be given in compressed format. Instead of giving the elements present in the array, we will be giving their frequencies. Formally, you will be given $m$, the maximum element in the array, and then $m + 1$ integers $f_0, f_1, \ldots, f_{m}$, where $f_i$ represents the number of times $i$ occurs in the array $a$.

$^\dagger$ The $\operatorname{MEX}$ (minimum excludant) of an array of integers is defined as the smallest non-negative integer which does not occur in the array. For example:

• The MEX of $[2,2,1]$ is $0$, because $0$ does not belong to the array.
• The MEX of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
• The MEX of $[0,3,1,2]$ is $4$, because $0$, $1$, $2$ and $3$ belong to the array, but $4$ does not.

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $m$ and $k$ ($1 \le m \le 2 \cdot 10^5, 1 \le k \le 10^9$).

The second line contains $m + 1$ integers $f_0, f_1, \ldots, f_m$ ($1 \le f_i \le 10^9$).

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

For each test case, find Alice's score if both players play optimally.

5
1 4
4 5
2 1000000000
1000000000 1000000000 1000000000
3 2
2 3 100 1
1 1
2 2
3 1
1 1 1 1

2
1
3
2
1

In the first test case, the array $a$ is $[0, 0, 0, 0, 1, 1, 1, 1, 1]$. A possible game with a score of $2$ is as follows:

1. Alice chooses the element $0$. After this move, $a = [0, 0, 0, 1, 1, 1, 1, 1]$ and $c=[0]$.
2. Bob chooses to remove the $3$ elements $0$, $0$ and $1$. After this move, $a = [0, 1, 1, 1, 1]$ and $c=[0]$.
3. Alice chooses the element $1$. After this move, $a = [0,1,1,1]$ and $c=[0,1]$.
4. Bob removes the $4$ remaining elements $0$, $1$, $1$ and $1$. After this move, $a=[\,]$ and $c=[0,1]$.

At the end, $c=[0,1]$ which has a MEX of $2$. Note that this is an example game and does not necessarily represent the optimal strategy for both players.

In the second test case, Alice can choose a $0$ in her first turn, guaranteeing that her score is at least $1$. While Bob can remove all copies element $1$ in his first turn, thus guaranteeing that Alice's score cannot exceed $1$. So Alice's score is $1$ if both players play optimally.