Crying 与 404

题号：NC264886
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

Crying 在面对错误码 404 Not Found。

他有一个 $\{0, 1, \dots, n-1\}$ 的排列 $\pi_1, \pi_2, \dots, \pi_n$ 。他每次会在一个区间里尝试找数，但总是找不到。所以他需要你来帮他解决一些问题。

他会进行 $m$ 次询问，每次询问给出 $l, r, k$ ，意味着他希望你告诉他第 $k$ 小的不能在集合 $\{\pi_l, \pi_{l+1}, \dots, \pi_r\}$ 中找到的自然数。

第一行，两个正整数 $n, m$ 。

第二行， $n$ 个非负整数 $\pi_1, \pi_2, \dots, \pi_n$ 。

以下 $m$ 行，每行三个正整数 $l, r, k$ 。

对于所有数据，保证 $1 \le n, m \le 5 \times 10^5$ ， $0 \le \pi_i < n$ ，所有 $\pi_i$ 互不相同， $1 \le l \le r \le n$ ， $1 \le k \le 10^{18}$ 。

 行，每行一个非负整数，依次表示每次询问的答案。

示例1

复制

复制

$\{0, 4, 2\}$ 中未出现的自然数从小到大有 $1, 3, 5, 6, 7, 8, \dots$ 。

$\{4, 2\}$ 中未出现的自然数从小到大有 $0, 1, 3, 5, 6, 7, 8, \dots, 11, \dots, 1001, \dots$ 。