你知道 Just Odd Inventions 公司嗎？這間公司的業務是進行「純粹奇怪的發明」。以下簡稱為 JOI 公司。

JOI 公司為了擴大業務，決定聘用新的員工。

共有 $N$ 位候選人，分別編號為 $1$ 到 $N$，每位候選人都有一個稱為評價值的整數。

本次招聘將錄用所有評價值不低於某個數值的候選人，並將新錄用的員工分成若干組。分組必須滿足以下條件：

• 當候選人 $a$ 與候選人 $b$（$a < b$）都被錄用時，這兩位員工被分在同一組，若且唯若候選人 $c$（$a \le c \le b$）全部都被錄用。

身為 JOI 公司的人事負責人，你將依序處理共 $M$ 個查詢，以估算本次招聘所形成的組數。第 $j$ 個查詢是以下兩種類型之一：

• 求出錄用所有評價值不低於 $B_j$ 的候選人時形成的組數。這類查詢稱為答案查詢。
• 將候選人 $C_j$ 的評價值更新為 $D_j$。這類查詢稱為更新查詢。

任務

給定 $M$ 個查詢的資訊，請寫一個程式，求出每個答案查詢所對應的組數。

輸入格式

從標準輸入讀取以下資料。

• 第一行包含以空格分隔的整數 $N,M$，表示共有 $N$ 位候選人，且你要處理 $M$ 個查詢。
• 接下來 $N$ 行中的第 $i$ 行（$1 \le i \le N$）包含一個整數 $A_i$，表示處理查詢之前，候選人 $i$ 的評價值為 $A_i$。

• 接下來 $M$ 行中的第 $j$ 行（$1 \le j \le M$）包含 2 個或 3 個以空格分隔的整數。令第一個整數為 $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 \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$）。
• 至少存在一個 $j$（$1 \le j \le M$）使得 $T_j = 1$。

子任務

子任務 1 [10 分]

滿足以下條件。

• $N \le 2\,000$。
• $M \le 2\,000$。

子任務 2 [30 分]

• 滿足 $T_j = 1$（$1 \le j \le 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. 第一個查詢是答案查詢。錄用評價值不低於 $5$ 的候選人 $1$、候選人 $2$、候選人 $4$ 時，會形成由候選人 $1$ 和候選人 $2$ 組成的一組，以及由候選人 $4$ 組成的一組，共 $2$ 組，因此輸出 $2$。
2. 第二個查詢是更新查詢，將候選人 $4$ 的評價值更新為 $1$。
3. 第三個查詢是答案查詢。錄用評價值不低於 $5$ 的候選人 $1$ 和候選人 $2$ 時，會形成由這兩位候選人組成的 $1$ 組，因此輸出 $1$。
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