극솟값 제거

서로 다른 정수로 이루어진 길이 $N$의 수열 $A = \left[ A_1, A_2, \cdots, A_N \right]$이 주어진다.

수열 $B$에 대해, 다음 과정을 한 번의 변화라고 하자.

• $B = \left[ B_1, B_2, \cdots, B_K \right]$라고 하자. 각 정수 $i$ $(2 \le i \le K - 1)$에 대하여, $B_{i - 1} > B_i < B_{i + 1}$를 만족할 때 $B_i$를 제거할 원소라고 하자. 수열 $B$에서 제거할 원소들을 모두 동시에 제거한 뒤, 남은 원소들을 순서를 유지하여 다시 붙인다.

예를 들어, 수열 $[5, 1, 3, 2, 4]$에 변화를 $3$번 적용하면 다음과 같이 변한다.

$$ [5, 1, 3, 2, 4] \rightarrow [5, 3, 4] \rightarrow [5, 4] \rightarrow [5, 4] $$

$Q$개의 쿼리가 주어진다. 각 쿼리는 세 정수 $l$, $r$, $t$로 표현할 수 있다. 각 쿼리 $(l, r, t)$에 대하여, 수열 $\left[ A_l, A_{l + 1}, \cdots, A_r \right]$에 변화를 $t$번 적용한 후, 이 수열에 남아 있는 원소의 개수를 구하라.

• 주어지는 모든 수는 정수이다.
• $1 \le N \le 200\,000$
• $1 \le Q \le 200\,000$
• 수열 $A$는 $1, 2, \cdots, N$의 순열이다. 즉, $\left\{ A_1, A_2, \cdots, A_N \right\} = \left\{ 1, 2, \cdots, N \right\}$
• 각 쿼리에 대하여, $1 \le l \le r \le N$
• 각 쿼리에 대하여, $1 \le t \le N$

1. (6점) $N \le 5\,000$; 각 쿼리에 대하여, $l = 1$과 $r = N$을 만족한다.
2. (11점) 각 쿼리에 대하여, $l = 1$과 $r = N$을 만족한다.
3. (6점) 각 쿼리에 대하여, $t = 1$
4. (12점) 각 쿼리에 대하여, $t = N$

5. (7점) 어떤 정수 $p$ ($1 \le p \le N$)가 존재하여 다음 조건을 모두 만족한다.

   • 정수 $i$ $(1 \le i \le p - 1)$에 대하여 $A_i > A_{i + 1}$
   • 정수 $i$ $(p \le i \le N - 1)$에 대하여 $A_i < A_{i + 1}$
6. (26점) 수열 $A = \left[ A_1, A_2, \cdots, A_N \right]$에 변화를 $20$번 적용한 뒤에는, 변화를 추가로 적용해도 수열이 바뀌지 않는다.
7. (32점) 추가 제약 조건 없음.

첫 줄에 두 정수 $N$과 $Q$가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 차례대로 주어진다.

그다음 $Q$개의 줄에 걸쳐, $Q$개의 쿼리에 대한 정보가 주어진다. 각 줄에는 하나의 쿼리를 나타내는 세 정수 $l$, $r$, $t$가 공백으로 구분되어 차례대로 주어진다.

첫 줄부터 $Q$개의 줄에 걸쳐, $Q$개의 쿼리에 대한 답을 출력한다. 입력에 주어진 순서대로, 쿼리마다 답을 한 줄에 하나씩 출력한다.