时空限制

1S/512M

题目描述

其实这题原本是投的 Round40 D，但是标程假了……
『复生』

为了争夺美味的沙威玛，apiadu 和 jiangly 准备来一场决斗博弈分分高下。

决斗场地可以表示为一个长度为 $n$ 的序列 $a$，一开始场上有一个棋子，先由 apiadu 决定一开始棋子的位置， 再由 jiangly 决定谁是先手。每次操作可以向左边或右边移动一步，两人交替进行。进行完 $x$ 轮操作后（每个人操作一次算一轮），棋子位置上的数就是得分，apiadu 希望得分尽可能小，jiangly 希望得分尽可能大。

有 $q$ 次询问，每次查询对于给定的 $x, l, r$。求若 apiadu 选的位置必须在 $[l, r]$ 内，且 apiadu 和 jiangly 按最优方式操作时，最终得分为多少。

格式

输入格式

第一行两个整数 $n, q$。

第二行包含 $n$ 个整数 $a_1,a_2 ,\dots a_n$。

接下来 $q$ 行, 每行三个整数 $x, l, r$, 表示一次询问，具体含义见题目描述。

输出格式

$q$ 行表示每次询问的答案。

样例

样例输入 #1

5 4
3 1 2 4 5
1 2 4
5 1 4
2 3 5
0 1 5

样例输出 #1

3
1
3
1

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$2 \le n \le 10^5, 1 \le q \le 10^5, 0 \le x \le n, 1 \le l \le r \le n, 1 \le a_i \le 10^8$。