시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 6 5 5 83.333%

문제

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

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

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

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

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

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

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

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

입력

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

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

출력

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

제한

  • 1 ≦ N ≦ 200 000.
  • 1 ≦ M ≦ 200 000.
  • 1 ≦ Ai ≦ 1 000 000 000 (1 ≦ i ≦ N).
  • 1 ≦ Tj ≦ 2 (1 ≦ j ≦ M).
  • 1 ≦ Bj ≦ 1 000 000 000 (1 ≦ j ≦ M).
  • 1 ≦ Cj ≦ N (1 ≦ j ≦ M).
  • 1 ≦ Dj ≦ 1 000 000 000 (1 ≦ j ≦ M).
  • Tj = 1 となる j (1 ≦ j ≦ M) は少なくとも一つ存在する.

예제 입력 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

예제 입력 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