Interval Mex

题号：NC236456
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld

题目描述

For any multiset $S$ ( $S$ may contain duplicated elements) of non-negative integers, define $\text{mex}(S)$ as the smallest non-negative integer that is not in $S$ .

You are given a sequence of $n$ non-negative integers $A_1,A_2,\ldots,A_n$ and $q$ queries.

For any interval $[l,r]$ ( $1\leq l\leq r\leq n$ ), let its weight be $\text{mex}([l,r])=\text{mex}(\lbrace A_l,A_{l+1},\cdots,A_r\rbrace)$ .

For each query, you are given an interval $[L, R]$ and a positive integer $k$ . Find the $k$ -th smallest weight among all subintervals of $[L, R]$ .

输入描述:

The first line contains two integers  (), denoting the length of the sequence and the number of queries.

The second line contains  non-negative integers  () separated by spaces.

In the following  lines, each line contains three integers  (), denoting a query.

输出描述:

Output  lines. The -th line should contain the answer of the -th query.

示例1

输入

复制

输出

复制