3905. [CF1852A] Ntarsis Set

【题目描述】

Ntarsis 有一个集合 $S$, 一开始 $S$ 包含 $1,2,3,\dots, 10^{100}$.

每天能进行 $n$ 个操作, Ntarsis 会同时删掉 $S$ 中第 $a_1$ 小的元素, 第 $a_2$ 小的元素, ..., 第 $a_n$ 小的元素.

Ntarsis 想知道, 经过 $k$ 天后, $S$ 中最小的元素是什么.

【输入格式】

第一行两个整数 $n, k$.

第二行 $n$ 个整数, 表示序列 $a[1:n]$, 保证 $a$ 严格单调递增, 即 $a_1\lt a_2\lt a_3 \lt \dots \lt a_n$.

【输出格式】

一个整数, 表示 $k$ 天后 $S$ 中最小的元素.

【样例输入 1】

5 1
1 2 4 5 6

【样例输出 1】

3

【样例输入 2】

10 6
1 4 7 10 13 16 19 22 25 28

【样例输出 2】

18

【样例输入 3】

9 1434
1 4 7 9 12 15 17 18 20

【样例输出 3】

12874

【样例说明】

第一个样例中, 每天第 $1, 2, 4, 5, 6$ 小的元素会被移除. 所以第一天后, $S$ 会变成 $\require{cancel} \{\cancel{1},\cancel{2},3,\cancel{4},\cancel{5},\cancel{6},7,8,9,\dots \}=\{3,7,8,9,\dots \}$. 最小的元素是 $3$.

【数据规模与约定】

对于 $30\%$ 的数据, 满足 $1\le n, k\le 50$.

另有 $10\%$ 的数据, 满足 $a_1 \gt 1$.

对于 $100\%$ 的数据, $1\le n, k\le 2\times 10^5, 1\le a_i\le 10^9$.