Problem Statement

You are given a permutation $A = \{ a_1, a_2, ... , a_N \} \ $ with $N$ elements.

A total of $Q$ queries of the following 1 type are given, so process them in order.

• $1 \ l \ r$

  • Let $A[l:r]$ be the sequence consisting of the $l$-th through $r$-th elements of $A$.
  • Output the number of high elements contained in $A[l:r]$.
  • Here, the $i$-th term of a sequence is said to be high if that term is the maximum among the $1$-st through $i$-th terms of the sequence.

Input

$N \ Q$
$a_1 \ a_2 \ \cdots \ a_N$
$query_1$
$query_2$
$\cdots$
$query_Q$

The first line contains an integer $N$ representing the length of the sequence and an integer $Q$ representing the number of queries, in this order, separated by a single-byte space.

The second line contains $N$ integers separated by single-byte spaces, where the $i$-th integer $(1 \le i \le N)$ represents the initial value of $a_i$.

The $i$-th $(1 \le i \le Q)$ of the following $Q$ lines contains the $i$-th query.

Each query is given in one of the following formats:

• $1 \ l \ r$

The input consists of $Q + 2$ lines in total and satisfies the following constraints.

• All input values are integers.
• $1 \le N, Q \le 10^5$
• $1 \le a_i \le N \ \ (1 \le i \le N)$
• $a_i \neq a_j \ \ (i \neq j)$
• Query 1
  • $1 \le l \le r \le N$

Output

For each query 1, output the number of high elements contained in $A[l:r]$, separated by newlines.

Sample

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

1
1
3
3
2