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.