hy的微机原理
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}Mr.Wang 在微信群中发布了 n 个整数 a_1,a_2,\dots,a_n,他宣布自己将会进行 k 轮检查,每一轮检查分为以下三个步骤,依次进行:
\hspace{23pt}\bullet\,依次检查当前仍未检查的同学中,排在第 a_1,a_2,\dots,a_n 位的同学的作业;
\hspace{23pt}\bullet\,将本轮检查过的这 n 名同学全部移出,不再参与后续检查;
\hspace{23pt}\bullet\,剩余同学自动重新编号(如剩余同学原编号为 3,7,8,\dots,则下一轮中他们的位置依次为第 1,2,3,\dots 位)
\hspace{15pt}假设同学们极多(比如 10^{1\,000\,000} 个),他们排成一整列,等待老师的检查。
\hspace{15pt}为了避免被检查,hy希望选择一个位置,使得在上述所有 k 轮检查中不会被检查到。如果存在多个位置,他希望排在最前面的那个位置。

本题纯净版 Markdown 提供如下。
# B.hy的微机原理

## 题目描述

$\hspace{15pt}$Mr.Wang 在微信群中发布了 $n$ 个整数 $a_1,a_2,\dots,a_n$,他宣布自己将会进行 $k$ 轮检查,每一轮检查分为以下三个步骤,依次进行:
$\hspace{23pt}\bullet\,$依次检查当前仍未检查的同学中,排在第 $a_1,a_2,\dots,a_n$ 位的同学的作业; 
$\hspace{23pt}\bullet\,$将本轮检查过的这 $n$ 名同学全部移出,不再参与后续检查;
$\hspace{23pt}\bullet\,$剩余同学自动重新编号(如剩余同学原编号为 $3,7,8,\dots$,则下一轮中他们的位置依次为第 $1,2,3,\dots$ 位)
$\hspace{15pt}$假设同学们极多(比如 $10^{1\,000\,000}$ 个),他们排成一整列,等待老师的检查。  
$\hspace{15pt}$为了避免被检查,hy希望选择一个位置,使得在上述所有 $k$ 轮检查中不会被检查到。如果存在多个位置,他希望排在最前面的那个位置。

## 输入描述

$\hspace{15pt}$第一行输入两个整数 $n,k \left(1 \leq n,k \leq 2 \times 10^5\right)$,表示同学人数和检查轮数。  
$\hspace{15pt}$第二行输入 $n$ 个递增排列的整数 $a_1,a_2,\dots,a_n \left(1 \leq a_i \leq 10^9\right)$,每一轮检查同学的编号。

## 输出描述

$\hspace{15pt}$输出一个整数,代表hy希望的排在最前面的、不会被检查到的位置编号。

## 样例

~~~text input:#1
5 1
1 2 4 5 6
~~~

~~~text output:#1
3
~~~

~~~text input:#2
4 3010
2 3 4 5
~~~

~~~text output:#2
1
~~~

~~~text input:#3
9 7
1 3 5 6 11 12 14 19 20
~~~

~~~text output:#3
42
~~~

输入描述:

\hspace{15pt}第一行输入两个整数 n,k \left(1 \leq n,k \leq 2 \times 10^5\right),表示同学人数和检查轮数。 
\hspace{15pt}第二行输入 n 个递增排列的整数 a_1,a_2,\dots,a_n \left(1 \leq a_i \leq 10^9\right),每一轮检查同学的编号。

输出描述:

\hspace{15pt}输出一个整数,代表hy希望排在最前面的那个位置对应的编号。
示例1

输入

复制
5 1
1 2 4 5 6

输出

复制
3
示例2

输入

复制
4 3010
2 3 4 5

输出

复制
1
示例3

输入

复制
9 7
1 3 5 6 11 12 14 19 20

输出

复制
42