Do you know the company "Just Odd Inventions"? The business of this company is to create "just odd inventions." We will call it the JOI company for short.

To expand its business, the JOI company has decided to hire new employees.

There are $N$ candidates for employees. Each candidate is assigned a number from $1$ to $N$, and each candidate is assigned an integer called an evaluation value.

In this hiring process, all candidates whose evaluation value is at least a certain value will be hired. The newly hired employees are divided into several groups. The groups of newly hired employees are formed to satisfy the following condition:

• When both candidate $a$ and candidate $b$ ($a < b$) are hired, these employees are in the same group if and only if all candidates $c$ ($a \le c \le b$) are also hired.

As the person in charge of human resources at the JOI company, you are to estimate the number of groups formed in this hiring process by processing a total of $M$ queries in order. The $j$-th query is one of the following two types:

• Find the number of groups formed when all candidates with an evaluation value of at least $B_j$ are hired. This type of query is called an answer query.
• Update the evaluation value of candidate $C_j$ to $D_j$. This type of query is called an update query.

Task

Given information about $M$ queries, write a program that calculates the number of groups for each answer query.

Input

Read the following data from standard input:

• The first line contains two space-separated integers $N$ and $M$. This indicates that there are $N$ candidates and you will process $M$ queries.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains an integer $A_i$. This indicates that before processing any queries, the evaluation value of candidate $i$ is $A_i$.
• The $j$-th line of the following $M$ lines ($1 \le j \le M$) contains two or three space-separated integers. Let the first integer be $T_j$. The content of this line is one of the following:
  1. If $T_j = 1$, this line contains integers $T_j$ and $B_j$ separated by a space. This indicates that the $j$-th query is an answer query to find the number of groups formed when all candidates with an evaluation value of at least $B_j$ are hired.
  2. If $T_j = 2$, this line contains integers $T_j$, $C_j$, and $D_j$ separated by a space. This indicates that the $j$-th query is an update query to update the evaluation value of candidate $C_j$ to $D_j$.

Output

Output the number of groups for each answer query to standard output, one per line.

Constraints

All input data satisfies the following conditions:

• $1 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le T_j \le 2$ ($1 \le j \le M$).
• $1 \le B_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• $1 \le C_j \le N$ ($1 \le j \le M$).
• $1 \le D_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• There is at least one $j$ ($1 \le j \le M$) such that $T_j = 1$.

Subtasks

Subtask 1 [10 points]

The following conditions are satisfied: $N \le 2\,000$. $M \le 2\,000$.

Subtask 2 [30 points]

• $T_j = 1$ ($1 \le j \le M$) is satisfied.

Subtask 3 [60 points]

There are no additional constraints.

Examples

Input 1

5 4
8
6
3
5
4
1 5
2 4 1
1 5
1 3

Output 1

2
1
2

Note

1. The first query is an answer query. If candidates 1, 2, and 4 (who have evaluation values of at least 5) are hired, a group consisting of candidate 1 and candidate 2, and a group consisting of candidate 4 are formed, so output 2.
2. The second query is an update query. Update the evaluation value of candidate 4 to 1.
3. The third query is an answer query. If candidates 1 and 2 (who have evaluation values of at least 5) are hired, one group consisting of candidate 1 and candidate 2 is formed, so output 1.
4. The fourth query is an answer query. If candidates 1, 2, 3, and 5 (who have evaluation values of at least 3) are hired, a group consisting of candidates 1, 2, and 3, and a group consisting of candidate 5 are formed, so output 2.

Input 2

7 5
13
19
1
15
13
1
19
1 20
1 1
1 6
1 11
1 17

Output 2

0
1
3
3
2

Note

Input 2 satisfies the constraints of Subtask 2.

Input 3

10 5
8
10
15
2
2
8
5
12
11
4
1 5
2 8 4
1 12
2 5 11
1 16

Output 3

2
1
0