AT_joi2023_yo2_e 日本沈没 2 (Japan Sinks 2)

日本列島は東西に細長い列島である．日本列島は南北方向の境界線により $ N $ 個の区画に分けられている．区画には西から順に $ 1 $ から $ N $ までの番号が付けられている．現在，区画 $ i $ ( $ 1 \leqq i \leqq N $ ) の標高は $ A_i \: \mathrm{m} $ である． 日本列島ではたびたび嵐が起きている．嵐が起きると波による浸食で各区画の標高が以下のように減少する． - 強さ $ x $ の**西風の**嵐では，西から数えて $ x $ 個以内の区画のうち，「それより西に自身より標高の高い区画が存在しない」ようなすべての区画の標高が $ 1 \: \mathrm{m} $ 減少する．すなわち，嵐の前の区画 $ i $ の標高を $ a_i $ で表すと， $ i \leqq x $ かつ， $ 1 \leqq k \lt i $ となるすべての $ k $ に対して $ a_k \leqq a_i $ となる場合に区画 $ i $ の標高は $ 1 \: \mathrm{m} $ 減り，それ以外の場合には変わらない． - 強さ $ x $ の**東風の**嵐では，東から数えて $ x $ 個以内の区画のうち，「それより東に自身より標高の高い区画が存在しない」ようなすべての区画の標高が $ 1 \: \mathrm{m} $ 減少する．すなわち，嵐の前の区画 $ i $ の標高を $ a_i $ で表すと， $ i \geqq N - x + 1 $ かつ， $ i \lt k \leqq N $ となるすべての $ k $ に対して $ a_k \leqq a_i $ となる場合に区画 $ i $ の標高は $ 1 \: \mathrm{m} $ 減り，それ以外の場合には変わらない． あなたは，今後 $ Q $ 日間の出来事をシミュレーションしなければならない． $ j $ 日目 ( $ 1 \leqq j \leqq Q $ ) には次のような出来事が起きる． - $ T_j = 1 $ のとき，強さ $ X_j $ の西風の嵐が起きる． - $ T_j = 2 $ のとき，強さ $ X_j $ の東風の嵐が起きる． - $ T_j = 3 $ のとき，その時点での区画 $ X_j $ の標高を報告する． なお，制約より，どの区画の標高も負にならないことが保証される． 現在の各区画の標高および今後 $ Q $ 日間の出来事が与えられるので， $ T_j = 3 $ である日に対して，指定された区画の標高を求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ T_1 $ $ X_1 $ $ T_2 $ $ X_2 $ $ \vdots $ $ T_Q $ $ X_Q $

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

### 小課題 1. ( $ 5 $ 点) $ N \leqq 2\,000 $ ， $ Q \leqq 2\,000 $ ． 2. ( $ 27 $ 点) $ T_j \neq 3 $ ならば $ X_j = N $ ( $ 1 \leqq j \leqq Q $ ). 3. ( $ 28 $ 点) $ A_1 = A_2 = \cdots = A_N = Q $ ． 4. ( $ 20 $ 点) $ T_j \neq 2 $ ( $ 1 \leqq j \leqq Q $ )． 5. ( $ 20 $ 点) 追加の制約はない． ### Sample Explanation 1 区画 $ 1, 2, 3, 4, 5 $ の標高 $ (\mathrm{m}) $ 出来事 開始時 $ 7, 7, 7, 7, 7 $ $ 1 $ 日目 強さ $ 3 $ の西風の嵐が起きる． 西から $ 3 $ 個以内の区画で，「それより西に自分より標高の高い区画が存在しない」ものは区画 $ 1, 2, 3 $ である． $ 6, 6, 6, 7, 7 $ $ 2 $ 日目 強さ $ 1 $ の西風の嵐が起きる． 西から $ 1 $ 個以内の区画で，「それより西に自分より標高の高い区画が存在しない」ものは区画 $ 1 $ のみである． $ 5, 6, 6, 7, 7 $ $ 3 $ 日目 区画 $ 1 $ の標高は現在 $ 5 \: \mathrm{m} $ なので， $ 5 $ を出力する． $ 5, 6, 6, 7, 7 $ $ 4 $ 日目 強さ $ 1 $ の東風の嵐が起きる． 東から $ 1 $ 個以内の区画で，「それより東に自分より標高の高い区画が存在しない」ものは区画 $ 5 $ のみである． $ 5, 6, 6, 7, 6 $ $ 5 $ 日目 強さ $ 5 $ の東風の嵐が起きる． 東から $ 5 $ 個以内の区画で，「それより東に自分より標高の高い区画が存在しない」ものは区画 $ 4, 5 $ のみである． $ 5, 6, 6, 6, 5 $ $ 6 $ 日目 区画 $ 2 $ の標高は現在 $ 6 \: \mathrm{m} $ なので， $ 6 $ を出力する． $ 5, 6, 6, 6, 5 $ $ 7 $ 日目 区画 $ 4 $ の標高は現在 $ 6 \: \mathrm{m} $ なので， $ 6 $ を出力する． この入力例は小課題 $ 1, 3, 5 $ の制約を満たす． ### Sample Explanation 2 この入力例は小課題 $ 1, 2, 5 $ の制約を満たす． ### Sample Explanation 3 この入力例は小課題 $ 1, 4, 5 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 1, 5 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 300\,000 $ ． - $ 1 \leqq Q \leqq 300\,000 $ ． - $ Q \leqq A_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq T_j \leqq 3 $ ( $ 1 \leqq j \leqq Q $ )． - $ 1 \leqq X_j \leqq N $ ( $ 1 \leqq j \leqq Q $ )． - 入力される値はすべて整数である．