Employment (Translated)

JOI Spring Training Camp 2015/16
Original Statement / Submission Site

Problem Statement

Have you heard of the company Just Odd Inventions? As its name suggests, the company's business is to create "just odd inventions." We will simply call it JOI.

JOI has decided to hire new employees to expand its business. There are N candidates, numbered from 1 to N. Each candidate has an integer called an evaluation value.

For this recruitment, all candidates whose evaluation value is at least a given threshold will be hired. The newly hired employees are divided into groups satisfying the following condition:

• If candidates a and b (a < b) are both hired, they belong to the same group if and only if every candidate c with a ≤ c ≤ b is also hired.

You must process M queries. Each query is one of the following:

• Answer Query: Given B, hire every candidate whose evaluation value is at least B and output the number of groups formed.
• Update Query: Change the evaluation value of candidate C to D.

Task

Given the initial evaluation values and the sequence of queries, output the number of groups for every answer query.

Input

The input is given as follows:

• The first line contains two integers N and M.
• The next N lines each contain A_i, the initial evaluation value of candidate i.
• Each of the following M lines describes one query:
  • 1 B: answer query.
  • 2 C D: update query.

Output

For each answer query, output the number of groups on its own line.

Constraints

• 1 ≤ N ≤ 200,000
• 1 ≤ M ≤ 200,000
• 1 ≤ A_i ≤ 1,000,000,000
• 1 ≤ B, D ≤ 1,000,000,000
• 1 ≤ C ≤ N
• There is at least one answer query.

Subtasks

• Subtask 1 [10 points]: N ≤ 2,000, M ≤ 2,000.
• Subtask 2 [30 points]: All queries are answer queries.
• Subtask 3 [60 points]: No additional constraints.

Sample Input 1

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

Sample Output 1

2
1
2

Explanation of Sample Output 1

1. The first query is an answer query. Hiring candidates 1, 2, and 4 forms two groups: {1,2} and {4}. Therefore the answer is 2.
2. The second query updates candidate 4's evaluation value to 1.
3. The third query hires candidates 1 and 2 only, so one group is formed.
4. The fourth query hires candidates 1, 2, 3, and 5, forming two groups: {1,2,3} and {5}.

Sample Input 2

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

Sample Output 2

0
1
3
3
2

Sample Input 2 satisfies the constraints of Subtask 2.

Sample 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

Sample Output 3

2
1
0