004 - 雇用計画 (Employment)

問題

あなたは Just Odd Inventions 社を知っているだろうか？この会社の業務は「ただ奇妙な発明（just odd inventions)」をすることである．ここでは略して JOI 社と呼ぶ．

JOI 社は事業を拡大するため，新たに社員を雇用することになった．

社員の候補者が N 人いる．候補者にはそれぞれ 1 から N までの番号が付けられており，それぞれの候補者には 評価値 と呼ばれる一つの整数が定められている．

今回の雇用では，評価値がある値以上の候補者を全員採用する．新たに採用された社員をいくつかのグループに分ける．新たに採用された社員のグループを，次の条件をみたすように作る．

• 候補者 a と候補者 b (a < b) が両方とも採用されたとき，これらの社員が同じグループに入るのは，候補者 c (a ≤ c ≤ b) が全員採用された場合であり，かつそのときに限る．

JOI 社の人事担当であるあなたは，クエリを合計 M 個順に処理することで，今回の雇用において作られるグループの個数を見積もることになった．j 番目のクエリは，以下の 2 種類のうちのいずれかである．

• 評価値が B_j 以上の候補者を全員採用する場合に作られるグループの個数を求める．この種類のクエリを 解答クエリ と呼ぶ．
• 候補者 C_j の評価値を D_j に更新する．この種類のクエリを 更新クエリ と呼ぶ．

課題

M 個のクエリについての情報が与えられたとき，それぞれの解答クエリに対するグループの個数を求めるプログラムを作成せよ．

入力

標準入力から以下のデータを読み込め．

• 1 行目には，整数 N, M が空白を区切りとして書かれている．これは，社員の候補者が N 人いて，あなたが M 個のクエリを処理することを表す．
• 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には，整数 A_i が書かれている．これは，クエリを処理する以前は，候補者 i の評価値が A_i であることを表す．
• 続く M 行のうちの j 行目 (1 ≤ j ≤ M) には，2 個または 3 個の整数が空白を区切りとして書かれている．1 個目の整数を T_j とすると，この行の内容は以下のいずれかである．
1. T_j = 1 のとき．この行には整数 T_j, B_j が空白を区切りとして書かれている．これは，j 番目のクエリが，評価値が B_j 以上の候補者を全員採用する場合に作られるグループの個数を求める解答クエリであることを表す．
2. T_j = 2 のとき．この行には整数 T_j, C_j, D_j が空白を区切りとして書かれている．これは，j 番目のクエリが，候補者 C_j の評価値を D_j に更新する更新クエリであることを表す．

出力

標準出力に，それぞれの解答クエリに対するグループの個数を順に 1 行ずつ出力せよ，

制限

すべての入力データは以下の条件を満たす．

• 1 ≤ N ≤ 200 000．
• 1 ≤ M ≤ 200 000．
• 1 ≤ A_i ≤ 1 000 000 000 (1 ≤ i ≤ N)．
• 1 ≤ T_j ≤ 2 (1 ≤ j ≤ M)．
• 1 ≤ B_j ≤ 1 000 000 000 (1 ≤ j ≤ M)．
• 1 ≤ C_j ≤ N (1 ≤ j ≤ M)．
• 1 ≤ D_j ≤ 1 000 000 000 (1 ≤ j ≤ M)．
• T_j = 1 となる j (1 ≤ j ≤ M) は少なくとも一つ存在する．

小課題

小課題 1 [10 点]

以下の条件を満たす．

• N ≤ 2 000．
• M ≤ 2 000．

小課題 2 [30 点]

• T_j = 1 (1 ≤ j ≤ M) を満たす．

小課題 3 [60 点]

追加の制限はない．

入出力例

入力例 1

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

出力例 1

2
1
2

1. 1 番目のクエリは解答クエリである．評価値が 5 以上である候補者 1, 候補者 2, 候補者 4 を採用した場合，候補者 1 と候補者 2 からなるグループと，候補者 4 からなるグループの 2 個のグループが作られるので，2 を出力する．
2. 2 番目のクエリは更新クエリである．候補者 4 の評価値を 1 に更新する．
3. 3 番目のクエリは解答クエリである．評価値が 5 以上である候補者 1 と候補者 2 を採用した場合，候補者 1 と候補者 2 からなる 1 個のグループが作られるので，1 を出力する．
4. 4 番目のクエリは解答クエリである．評価値が 3 以上である候補者 1, 候補者 2, 候補者 3, 候補者 5 を採用した場合，候補者 1, 候補者 2, 候補者 3 からなるグループと，候補者 5 からなるグループの 2 個のグループが作られるので，2 を出力する．

入力例 2

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

出力例 2

0
1
3
3
2

入力例 2 は小課題 2 の制限を満たす．

入力例 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

出力例 3

2
1
0