311167: CF1943E2. MEX Game 2 (Hard Version)

E2. MEX Game 2 (Hard Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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

ExampleInput

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

Output

2
1
3
2
1

Note

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.

题目大意：

这个题目是“MEX游戏2”的困难版本。两个版本之间的唯一区别是对$t$、$m$以及$m$的和的约束。只有当两个版本的问题都解决时，你才能进行hack。

Alice和Bob在一个大小为$n$的数组$a$上玩另一个游戏。Alice从一个空数组$c$开始。两个玩家轮流进行游戏，Alice先开始。

在Alice的回合，她从$a$中选择一个元素，将其添加到$c$中，然后从$a$中删除它。

在Bob的回合，他从$a$中选择至多$k$个元素，然后从$a$中删除它们。

当数组$a$为空时，游戏结束。Alice的得分被定义为$c$的MEX（最小排除数）。Alice想要最大化她的得分，而Bob想要最小化得分。如果两个玩家都发挥最佳，找出Alice的最终得分。

数组将以压缩格式给出。不是直接给出数组中存在的元素，而是给出它们的出现频率。具体来说，你会得到$m$，数组中的最大元素，然后是$m + 1$个整数$f_0, f_1, \ldots, f_m$，其中$f_i$表示$i$在数组$a$中出现的次数。

MEX（最小排除数）的定义是数组中最小的非负整数，它不在数组中。例如：
- 数组$[2,2,1]$的MEX是$0$，因为$0$不属于该数组。
- 数组$[3,1,0,1]$的MEX是$2$，因为$0$和$1$属于该数组，但$2$不属于。
- 数组$[0,3,1,2]$的MEX是$4$，因为$0$、$1$、$2$和$3$属于该数组，但$4$不属于。

输入输出数据格式：

输入：

每个测试包含多个测试案例。第一行包含一个整数$t$（$1 \leq t \leq 10^5$）——测试案例的数量。接下来是测试案例的描述。

每个测试案例的第一行包含两个整数$m$和$k$（$1 \le m \le 2 \cdot 10^5, 1 \le k \le 10^9$）。

第二行包含$m + 1$个整数$f_0, f_1, \ldots, f_m$（$1 \le f_i \le 10^9$）。

保证所有测试案例的$m$之和不超过$2 \cdot 10^5$。

输出：

对于每个测试案例，如果两个玩家都发挥最佳，找出Alice的得分。

示例：

输入：
```
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
```

注意：这些示例并不一定代表两个玩家的最佳策略，只是可能的游戏过程。题目大意： 这个题目是“MEX游戏2”的困难版本。两个版本之间的唯一区别是对$t$、$m$以及$m$的和的约束。只有当两个版本的问题都解决时，你才能进行hack。 Alice和Bob在一个大小为$n$的数组$a$上玩另一个游戏。Alice从一个空数组$c$开始。两个玩家轮流进行游戏，Alice先开始。 在Alice的回合，她从$a$中选择一个元素，将其添加到$c$中，然后从$a$中删除它。 在Bob的回合，他从$a$中选择至多$k$个元素，然后从$a$中删除它们。 当数组$a$为空时，游戏结束。Alice的得分被定义为$c$的MEX（最小排除数）。Alice想要最大化她的得分，而Bob想要最小化得分。如果两个玩家都发挥最佳，找出Alice的最终得分。 数组将以压缩格式给出。不是直接给出数组中存在的元素，而是给出它们的出现频率。具体来说，你会得到$m$，数组中的最大元素，然后是$m + 1$个整数$f_0, f_1, \ldots, f_m$，其中$f_i$表示$i$在数组$a$中出现的次数。 MEX（最小排除数）的定义是数组中最小的非负整数，它不在数组中。例如： - 数组$[2,2,1]$的MEX是$0$，因为$0$不属于该数组。 - 数组$[3,1,0,1]$的MEX是$2$，因为$0$和$1$属于该数组，但$2$不属于。 - 数组$[0,3,1,2]$的MEX是$4$，因为$0$、$1$、$2$和$3$属于该数组，但$4$不属于。 输入输出数据格式： 输入： 每个测试包含多个测试案例。第一行包含一个整数$t$（$1 \leq t \leq 10^5$）——测试案例的数量。接下来是测试案例的描述。 每个测试案例的第一行包含两个整数$m$和$k$（$1 \le m \le 2 \cdot 10^5, 1 \le k \le 10^9$）。 第二行包含$m + 1$个整数$f_0, f_1, \ldots, f_m$（$1 \le f_i \le 10^9$）。 保证所有测试案例的$m$之和不超过$2 \cdot 10^5$。 输出： 对于每个测试案例，如果两个玩家都发挥最佳，找出Alice的得分。 示例： 输入： ``` 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 ``` 注意：这些示例并不一定代表两个玩家的最佳策略，只是可能的游戏过程。