21095번 - Best Subsequence 다국어

문제

We call $W$ a $k$-best number of sequence $B_{1...m}$ if there exists a sequence $C_{1...k}$ satisfying the following two conditions:

1. $C_{1...k}$ is a subsequence of $B_{1...m}$.
2. $\forall i \in [1, k], C_{i} + C_{(i \bmod k) + 1} \le W$.

Given a sequence $A_{1...n},ドル you need to answer $Q$ questions. Each question consists of three integers $L, R, K,ドル and you need to calculate the minimum $K$-best number of $A_{L...R}$.

Recall that $C$ is a subsequence of $B$ if and only if we can obtain $C$ by removing some elements of $B$ (possibly none or all).

입력

The first line contains two integers $n$ and $Q$ (1ドル \le n, Q \le 10^5$).

The second line contains $n$ integers $A_{1...n}$ (0ドル \le A_i \le 10^9$).

Then $Q$ lines follow. Each of them contains three integers $L, R, K,ドル representing a question (1ドル \le L \le R \le n$; 1ドル \le K \le R - L + 1$).

출력

For each question, output a single line with a single integer: the answer.

제한

힌트