Problem Description

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<B_{i+1}$ ($2 \le i \le K-1$), call $B_i$ an element to be deleted. Delete all elements to be deleted from $B$ simultaneously, then keep the relative order of the remaining elements and concatenate them.

For example, after applying the transformation three times to the sequence $[5,1,3,2,4]$, the sequence changes as follows:

You are given $Q$ queries. Each query consists of three integers $l,r,t$. For each query $(l,r,t)$, output the number of elements remaining in the sequence $[A_l,A_{l+1},\cdots,A_r]$ after applying the transformation $t$ times.

Input Format

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 Format

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.

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

3
2
3
3
2

15 7
14 5 2 7 11 13 3 12 9 4 10 8 1 6 15
1 15 1
1 15 2
1 15 3
1 15 4
1 15 5
1 15 6
1 15 7

11
8
6
4
3
2
2

10 10
9 6 4 1 8 2 3 5 7 10
1 10 1
1 10 2
1 10 5
1 9 3
2 10 2
2 10 4
3 8 1
3 8 2
1 5 4
4 8 3

8
6
2
3
5
3
4
3
2
3

Hint

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<A_{i+1}$.
6. ($26$ points) After applying $20$ transformations to the sequence $A=[A_1,A_2,\cdots,A_N]$, applying further transformations will not change the sequence anymore.
7. ($32$ points) No additional constraints.

Translated by ChatGPT-5.6.

Translated by ChatGPT 5