Codeforces Round 887 (Div. 2)

C. Ntarsis' Set

https://codeforces.com/contest/1853/problem/C

2 seconds / 256 megabytes

standard input / standard output

Problem

Ntarsis has been given a set $S$, initially containing integers $1, 2, 3, \ldots, 10^{1000}$ in sorted order. Every day, he will remove the $a_1$-th, $a_2$-th, $\ldots$, $a_n$-th smallest numbers in $S$ simultaneously.

What is the smallest element in $S$ after $k$ days?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case consists of two integers $n$ and $k$ ($1 \leq n,k \leq 2 \cdot 10^5$) — the length of $a$ and the number of days.

The following line of each test case consists of $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the elements of array $a$.

It is guaranteed that:

  • The sum of $n$ over all test cases won't exceed $2 \cdot 10^5$;
  • The sum of $k$ over all test cases won't exceed $2 \cdot 10^5$;
  • $a_1 < a_2 < \cdots < a_n$ for all test cases.

Output

For each test case, print an integer that is the smallest element in $S$ after $k$ days.

Example

Input

7
5 1
1 2 4 5 6
5 3
1 3 5 6 7
4 1000
2 3 4 5
9 1434
1 4 7 9 12 15 17 18 20
10 4
1 3 5 7 9 11 13 15 17 19
10 6
1 4 7 10 13 16 19 22 25 28
10 150000
1 3 4 5 10 11 12 13 14 15

Output

3
9
1
12874
16
18
1499986

Note

For the first test case, each day the $1$-st, $2$-nd, $4$-th, $5$-th, and $6$-th smallest elements need to be removed from $S$. So after the first day, $S$ will become $\require{cancel}$ $\{\cancel 1, \cancel 2, 3, \cancel 4, \cancel 5, \cancel 6, 7, 8, 9, \ldots\} = \{3, 7, 8, 9, \ldots\}$. The smallest element is $3$.

For the second case, each day the $1$-st, $3$-rd, $5$-th, $6$-th and $7$-th smallest elements need to be removed from $S$. $S$ will be changed as follows:

Day$S$ before$S$ after
1$\{\cancel 1, 2, \cancel 3, 4, \cancel 5, \cancel 6, \cancel 7, 8, 9, 10, \ldots \}$$\to \{2, 4, 8, 9, 10, \ldots\}$
2$\{\cancel 2, 4, \cancel 8, 9, \cancel{10}, \cancel{11}, \cancel{12}, 13, 14, 15, \ldots\}$$\to \{4, 9, 13, 14, 15, \ldots\}$
3$\{\cancel 4, 9, \cancel{13}, 14, \cancel{15}, \cancel{16}, \cancel{17}, 18, 19, 20, \ldots\}$$\to \{9, 14, 18, 19, 20, \ldots\}$

The smallest element left after $k = 3$ days is $9$.

题解

对于下面这个样例：

ID   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
a[]  1 _ _ _ _ _ 7 _ _ _  _  12 _  _  _  16

对于位置为 $2\sim 6$ 的数字，可能被位置 $1$ 删去，删完后后面的数往前移动 $1$ 位。

对于位置为 $8\sim11$ 的数字，可能被位置 $1,7$ 删去，删完后后面的数往前移动 $2$ 位（因为前面 $1$ 会删一个）。

对于位置为 $13\sim15$ 的数字，可能被位置 $1,7,12$ 删去，删完后后面的数往前移动 $3$ 位（因为前面 $1,7$ 会删两个）。

删除方式如下所示，如果被位置 $1$ 删掉标记 $a$，被位置 $7$ 删掉标记 $b$，以此类推：

ID   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
a[]  1 _ _ _ _ _ 7 _ _ _  _  12 _  _  _  16
del  a a a a a a b a b a  b  c  b  a  c  b

另外，位置 $1$ 在第 $k+1$ 次删去的位置便是本题答案。所以可以模拟 $k$ 次操作并维护 $1$ 每次删去的位置即可。

维护方式就是，初始位置 $pos=1$，每次跨越 $nxt=0$，每当位置 $1$ 每跨越一个 $a_i$ 时，$nxt+1$.

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int MAXN = 2e5 + 10;
int a[MAXN];

void solve()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 该特判其实可以删去，不过加上可以略微提速
    if (a[1] != 1)
    {
        cout << "1" << endl;
        return;
    }
    int pos = 1, nxt = 0;
    for (int i = 0; i < k; i++)
    {
        while (pos + nxt >= a[nxt + 1])
        {
            if (nxt >= n)
                break;
            nxt++;
        }
        pos += nxt;
    }
    cout << pos << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}