P14231 复读机 / repeat

模拟赛偶遇联考，子序列复读强如怪物，拼尽全力无法战胜。 并非偶遇，并非怪物，并非无法战胜。

给你一个长度为 $n$ 的序列 $a_{1\dots n}$。 接下来有 $q$ 次查询，每次给出一个区间 $[l,r]$ 和 $k$，你需要： - 在区间中选择一个长为 $k$ 的子序列，最小化相邻两项的和的最大值。 形式化地说，选择一组 $l\le p_1

第一行两个整数 $n,q$。 第二行 $n$ 个整数 $a_{1\dots n}$。 接下来 $q$ 行，每行 $3$ 个整数 $l,r,k$ 表示一次询问。

共 $q$ 行，每行一个整数表示答案。

### 数据范围与约定 **本题采用捆绑测试。** ::cute-table | 子任务编号 | $n\le$ | $q\le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $18$ | $18$ | 无 | $5$ | | $2$ | $40$ | $2\times10^5$ | ^ | $10$ | | $3$ | $1000$ | $1000$ | ^ | $5$ | | $4$ | $10^5$ | $10$ | ^ | $20$ | | $5$ | ^ | $2\times 10^5$ | $a_i\le 2$ | $15$ | | $6$ | ^ | ^ | $a_i\le 5$ | $15$ | | $7$ | ^ | ^ | 无 | $25$ | | $8$ | $3\times 10^5$ | $3\times 10^5$ | ^ | $5$ | 对于所有数据，保证 $1\le n,q\le 3\times 10^5$，$1\le a_i \le n$，$1\le l\le r\le n$，$2\le k\le r-l+1$。 **保证你在本场模拟赛的得分不超过 $\bm{998244853}$。**