JOI logo
第22回日本情報オリンピック 二次予選

2022年12月13日
情報オリンピック日本委員会

問題
  日本沈没 2 (Japan Sinks 2) (配点 100点)
  時間制限 : 3 sec / メモリ制限 : 1024 MB

問題文

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

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

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

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

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

制約

小課題

  1. (5 点) N ≦ 2 000Q ≦ 2 000
  2. (27 点) Tj ≠ 3 ならば Xj = N (1 ≦ j ≦ Q).
  3. (28 点) A1 = A2 = … = AN = Q
  4. (20 点) Tj ≠ 2 (1 ≦ j ≦ Q).
  5. (20 点) 追加の制約はない.

入力

入力は以下の形式で与えられる.
N Q
A1 A2 AN
T1 X1
T2 X2
:
TQ XQ

出力

Tj = 3 である j (1 ≦ j ≦ Q) それぞれに対して,j 日目時点での区画 Xj の標高 (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, 2, 3, 4, 5 の標高 (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 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 m なので,6 を出力する.
5, 6, 6, 6, 5
7 日目 区画 4 の標高は現在 6 m なので,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 の制約を満たす.