P17197 [KOI 2026 #2] Delete Local Minima.

You are given a sequence $A=[A_1,A_2,\cdots,A_N]$ of length $N$, consisting of pairwise distinct integers. For a sequence $B$, the following process is called one transformation: - Let $B=[B_1,B_2,\cdots,B_K]$. For every integer $i$ satisfying $B_{i-1}>B_i

The first line contains two integers $N$ and $Q$, separated by spaces. The second line contains $N$ integers $A_1,A_2,\cdots,A_N$, separated by spaces. The next $Q$ lines give the queries. Each line contains three integers $l,r,t$, separated by spaces, representing one query.

Output $Q$ lines of answers starting from the first line. Print each query’s answer on its own line, in the same order as the input.

### Constraints - All given numbers are integers. - $1 \le N \le 200\,000$. - $1 \le Q \le 200\,000$. - The sequence $A$ is a permutation of $1,2,\cdots,N$, i.e., $\{A_1,A_2,\cdots,A_N\}=\{1,2,\cdots,N\}$. - For each query, $1 \le l \le r \le N$. - For each query, $1 \le t \le N$. ### Subtasks 1. ($6$ points) $N \le 5\,000$; for each query, $l=1$ and $r=N$. 2. ($11$ points) For each query, $l=1$ and $r=N$. 3. ($6$ points) For each query, $t=1$. 4. ($12$ points) For each query, $t=N$. 5. ($7$ points) There exists an integer $p$ ($1 \le p \le N$) such that the following conditions both hold: - For every integer $i$ ($1 \le i \le p-1$), $A_i>A_{i+1}$. - For every integer $i$ ($p \le i \le N-1$), $A_i