Yesik 市的一条大街上种着 $n$ 棵树。从左往右数，第 $i$ 棵树的高度为 $a_i$。每一分钟结束时，会发生以下变换：
- 如果第 $i$ 棵树的邻居中至少有一棵比它高，那么第 $i$ 棵树的高度增加 1。更正式地说，需要满足 $a_{i-1} > a_i$ 或 $a_{i+1} > a_i$ 中的至少一个条件。这里我们假设 $a_0 = a_{n+1} = 0$。
注意，所有树的变换是同时发生的。例如，如果当前树的高度为 $[3, 3, 4, 2, 2]$，下一分钟高度将变为 $[3, 4, 4, 3, 2]$。
初始树高对应第 0 分钟。你需要回答 $q$ 个独立的查询，查询类型如下：
- 第 $t$ 分钟开始时，第 $x$ 棵树的高度是多少？
输入格式
第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$)，分别表示树的数量和查询的数量。
第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^{18}$，对于所有 $1 \le i \le n$)，表示所有树的初始高度。
接下来 $q$ 行，每行包含一对整数 $(x_i, t_i)$ ($1 \le x_i \le n, 0 \le t_i \le 10^{18}$)，表示查询的描述。
输出格式
按输入顺序输出 $q$ 个整数，即所有查询的答案。
子任务
| 子任务 | 附加约束 | 分值 | 必要子任务 |
|---|---|---|---|
| 0 | 样例 | 0 | — |
| 1 | $n \le 100, a_i \le 100$ (对于所有 $1 \le i \le n$) | 6 | 0 |
| 2 | $n \le 100$ | 21 | 1 |
| 3 | $n \le 2000$ | 20 | 2 |
| 4 | — | 53 | 3 |
样例
输入格式 1
5 4 1 3 2 5 1 3 0 1 3 3 2 5 2
输出格式 1
2 3 4 3
说明
样例中所有树的高度变化如下：
- 第 0 分钟：$[1, 3, 2, 5, 1]$；
- 第 1 分钟：$[2, 3, 3, 5, 2]$；
- 第 2 分钟：$[3, 3, 4, 5, 3]$；
- 第 3 分钟：$[3, 4, 5, 5, 4]$。