2168 - 日本沈没 2 (Japan Sinks 2)

問題文

日本列島は東西に細長い列島である．日本列島は南北方向の境界線により N 個の区画に分けられている．区画には西から順に 1 から N までの番号が付けられている．現在，区画 i (1 ≦ i ≦ N) の標高は A_i m である．

日本列島ではたびたび嵐が起きている．嵐が起きると波による浸食で各区画の標高が以下のように減少する．

• 強さ x の西風の嵐では，西から数えて x 個以内の区画のうち，「それより西に自身より標高の高い区画が存在しない」ようなすべての区画の標高が 1 m 減少する．すなわち，嵐の前の区画 i の標高を a_i で表すと，i ≦ x かつ，1 ≦ k ＜ i となるすべての k に対して a_k ≦ a_i となる場合に区画 i の標高は 1 m 減り，それ以外の場合には変わらない．
• 強さ x の東風の嵐では，東から数えて x 個以内の区画のうち，「それより東に自身より標高の高い区画が存在しない」ようなすべての区画の標高が 1 m 減少する．すなわち，嵐の前の区画 i の標高を a_i で表すと，i ≧ N - x + 1 かつ，i ＜ k ≦ N となるすべての k に対して a_k ≦ a_i となる場合に区画 i の標高は 1 m 減り，それ以外の場合には変わらない．

あなたは，今後 Q 日間の出来事をシミュレーションしなければならない．j 日目 (1 ≦ j ≦ Q) には次のような出来事が起きる．

• T_j = 1 のとき，強さ X_j の西風の嵐が起きる．
• T_j = 2 のとき，強さ X_j の東風の嵐が起きる．
• T_j = 3 のとき，その時点での区画 X_j の標高を報告する．

なお，制約より，どの区画の標高も負にならないことが保証される．

現在の各区画の標高および今後 Q 日間の出来事が与えられるので，T_j = 3 である日に対して，指定された区画の標高を求めるプログラムを作成せよ．

制約

• 1 ≦ N ≦ 300 000．
• 1 ≦ Q ≦ 300 000．
• Q ≦ A_i ≦ 10⁹ (1 ≦ i ≦ N)．
• 1 ≦ T_j ≦ 3 (1 ≦ j ≦ Q)．
• 1 ≦ X_j ≦ N (1 ≦ j ≦ Q)．
• 入力される値はすべて整数である．

小課題

1. (5 点) N ≦ 2 000，Q ≦ 2 000．
2. (27 点) T_j ≠ 3 ならば X_j = N (1 ≦ j ≦ Q).
3. (28 点) A₁ = A₂ = … = A_N = Q．
4. (20 点) T_j ≠ 2 (1 ≦ j ≦ Q)．
5. (20 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N Q
A₁ A₂ … A_N
T₁ X₁
T₂ X₂
:
T_Q X_Q

出力

T_j = 3 である j (1 ≦ j ≦ Q) それぞれに対して，j 日目時点での区画 X_j の標高 (m) を表す整数を，1 行ずつ順に出力せよ．

入出力例

入力例 1
5 7
7 7 7 7 7
1 3
1 1
3 1
2 1
2 5
3 2
3 4

出力例 1
5
6
6

この入力例は小課題 1, 3, 5 の制約を満たす．

入力例 2
5 7
10 13 14 7 12
1 5
2 5
3 3
3 4
2 5
3 1
3 2

出力例 2
12
7
9
11

この入力例は小課題 1, 2, 5 の制約を満たす．

入力例 3
5 6
8 6 7 8 9
1 1
3 1
3 5
1 3
3 2
3 3

出力例 3
7
9
6
6

この入力例は小課題 1, 4, 5 の制約を満たす．

入力例 4
5 6
6 8 6 9 7
2 1
2 4
3 5
1 5
3 4
3 3

出力例 4
5
7
6

この入力例は小課題 1, 5 の制約を満たす．