問題文

JOI 君は N 個の碁石を持っている．それぞれの碁石には 1 から N までの番号が付けられており，1 以上 10^9 以下の整数で表される色で塗られている．最初，碁石 i (1 \leqq i \leqq N) の色は A_i である．

JOI 君はこれから N 回の操作を行い，碁石をテーブルの上に 1 列に並べたい．i 回目 (1 \leqq i \leqq N) の操作は以下のような手順で行われる．

1. 碁石 i を碁石 i-1 の右隣に置く．ただし，i=1 の場合は，碁石 1 をテーブルの上に置く．
2. 碁石 1, 2, \dots, i-1 のうち現在の色が碁石 i と同じであるものが存在する場合，それらのうち番号が最も大きいものを j とすると，碁石 j+1, j+2, \dots, i-1 の色をすべて色 A_i に塗り替える．

操作を正しく行ったか確認するために，JOI 君はすべての操作を行った後の碁石の色を予め知っておきたい．

碁石の情報が与えられたとき，N 回の操作を行った後のそれぞれの碁石の色を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 200\,000．
• 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (25 点) N \leqq 2\,000．
2. (35 点) A_i \leqq 2 (1 \leqq i \leqq N)．
3. (40 点) 追加の制約はない．

入力例 1

6
1
2
1
2
3
2

出力例 1

1
1
1
2
2
2

操作は以下の表のように行われる．

最終的に，碁石 1，2，3，4，5，6 の色はそれぞれ 1，1，1，2，2，2 となる．

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

入力例 2

10
1
1
2
2
1
2
2
1
1
2

出力例 2

1
1
1
1
1
1
1
1
1
2

この入出力例はすべての小課題の制約を満たす．

問題文

JOI 国には N 人の住人がおり，1 から N までの番号が付けられている． 住人 i (1 \leqq i \leqq N) は数直線上の座標 X_i に住んでおり，その影響力は E_i である．同じ座標に複数の住人が住んでいることもある． 影響力が高い住人ほど宣伝効果が大きい一方で，本を買うのに慎重になる．

理恵さんは情報科学の本を出版した．本を多くの人に買ってもらうため，何人かの住人に献本をすることができる． 住民 i (1 \leqq i \leqq N) に献本した場合，住人 i は理恵さんの本を手に入れる． さらに，まだ理恵さんの本を持っていない住人のうち，次の条件を満たすようなすべての住人 j (1 \leqq j \leqq N) は理恵さんの本を買って手に入れる．

• 住人 i と住人 j との数直線上での距離が E_i - E_j 以下である．すなわち |X_i - X_j| \leqq E_i - E_j である．

もし理恵さんの本が JOI 国のすべての住人に読まれれば，情報オリンピックの知名度は大きく向上するだろう． JOI 国の住人全員が理恵さんの本を手に入れるために，最小で何人に献本する必要があるかを求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 500\,000．
• 1 \leqq X_i \leqq 10^9 (1 \leqq i \leqq N)．
• 1 \leqq E_i \leqq 10^9 (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (10 点) E_1 = E_2 = \cdots = E_N．
2. (23 点) N \leqq 16．
3. (36 点) N \leqq 1\,000．
4. (31 点) 追加の制約はない．

入力例 1

4
4 2
2 3
3 4
6 5

出力例 1

2

たとえば次のように献本すると，JOI 国の住人全員が理恵さんの本を手に入れることができる．

• 住人 3 に献本する．

  • |X_3 - X_1| = 1, E_3 - E_1 = 2 より，住人 1 は理恵さんの本を買って手に入れる．
  • |X_3 - X_2| = 1, E_3 - E_2 = 1 より，住人 2 は理恵さんの本を買って手に入れる．
  • |X_3 - X_4| = 3, E_3 - E_4 = -1 より，住人 4 は理恵さんの本を買わない．

  よって，住人 1, 2, 3 が理恵さんの本を手に入れることになる．

• 住人 4 に献本する．住人 4 以外の住人はいずれも既に理恵さんの本を手に入れているので，これで JOI 国の住人全員が理恵さんの本を手に入れたことになる．

2 人未満への献本で JOI 国の住人全員が理恵さんの本を手に入れるようにすることはできないので，2 を出力する．
この入力例は小課題 2, 3, 4 の制約を満たす．

入力例 2

3
7 10
10 10
7 10

出力例 2

2

この入出力例はすべての小課題の制約を満たす．

入力例 3

10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019

出力例 3

5

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

問題文

迷路を解くのが好きな K 理事長は，迷路になりそうなマス目を見つけた．マス目は縦 R 行，横 C 列の長方形の形をしており，各マスは白または黒で塗られている．上から i 行目 (1 \leqq i \leqq R)，左から j 列目 (1 \leqq j \leqq C) のマスをマス (i, j) と呼ぶことにする．

K 理事長は，マス目の白いマスは通れるマス，黒いマスは通れないマスとして，迷路を解くことにした．具体的には，以下のようにして迷路を解く．

1. 白いマスの中からスタートのマス (S_r, S_c) とゴールのマス (G_r, G_c) を選ぶ．
2. 上下左右に隣接する白いマスに移動することを繰り返して，スタートのマスからゴールのマスへ移動する経路を見つける．

K 理事長はスタートのマスとゴールのマスを決めたが，マス目の色の塗られ方によっては，白いマスのみを通ってスタートからゴールへ移動する経路が存在しない場合があることに気がついた．そこで， K 理事長の持っている N \times N マスの大きさのハンコを用いて以下の操作を繰り返すことで，スタートからゴールへ移動する経路が存在するようにしたい．

操作：マス目から N \times N マスの正方形の領域を選び，この領域に含まれるマスをすべて白にする．より厳密には，1 \leqq a \leqq R - N + 1，1 \leqq b \leqq C - N + 1 を満たす整数 a, b を選び，a \leqq i \leqq a + N - 1，b \leqq j \leqq b + N - 1 を満たすすべての整数の組 (i, j) に対して，マス (i, j) を白にする．

ハンコを使うと手が汚れる可能性があるため，操作回数はできるだけ少なくしたい．マス目の塗られ方とハンコの大きさ，スタートのマスとゴールのマスが与えられたとき，白いマスのみを通ってスタートからゴールへ移動する経路が存在するようにするための，操作回数の最小値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq R \leqq C．
• R \times C \leqq 6\,000\,000．
• 1 \leqq S_r \leqq R．
• 1 \leqq S_c \leqq C．
• 1 \leqq G_r \leqq R．
• 1 \leqq G_c \leqq C．
• (S_r, S_c) \neq (G_r, G_c)．
• A_i (1 \leqq i \leqq R) は . または # からなる長さ C の文字列である．
• マス (S_r, S_c) の色は白である．
• マス (G_r, G_c) の色は白である．
• R, C, N, S_r, S_c, G_r, G_c は整数である．

小課題

1. (8 点) N = 1，R \times C \leqq 1\,500\,000．
2. (19 点) R \times C \leqq 1\,000．
3. (16 点) 答えは 10 以下である，R \times C \leqq 1\,500\,000．
4. (19 点) R \times C \leqq 60\,000．
5. (5 点) R \times C \leqq 150\,000．
6. (19 点) R \times C \leqq 1\,500\,000．
7. (8 点) R \times C \leqq 3\,000\,000．
8. (6 点) 追加の制約はない．

入力例 1

2 4 2
1 1
2 4
.###
###.

出力例 1

1

(a, b) = (1, 2) を選んで 1 回操作を行い，マス (1, 2), (1, 3), (2, 2), (2, 3) を白にすると，白いマスのみを通ってスタートからゴールへ移動する経路が存在するようになる．例えば，経路 (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 4) はその 1 つである．

操作を 1 回も行わない場合，白いマスのみを通ってスタートからゴールへ移動する経路は存在しないから，1 を出力する．

この入力例は小課題 2, 3, 4, 5, 6, 7, 8 の制約を満たす．

入力例 2

6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###

出力例 2

4

この入力例はすべての小課題の制約を満たす．

入力例 3

6 7 6
6 4
3 1
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.

出力例 3

1

この入力例は小課題 2, 3, 4, 5, 6, 7, 8 の制約を満たす．

入力例 4

1 15 1
1 15
1 1
...............

出力例 4

0

操作を 1 回も行わなくても，白いマスのみを通ってスタートからゴールへ移動する経路が存在する場合がある．

この入力例はすべての小課題の制約を満たす．

問題文

N 個のキャットタワーがあり，それぞれに 1 から N までの番号が付けられている． タワー i (1 \leqq i \leqq N) の高さは P_i である． タワーの高さは 1 以上 N 以下の相異なる整数である． N-1 組のタワーが隣接しており，各 j (1 \leqq j \leqq N-1) について， タワー A_j とタワー B_j が隣接している． はじめ，どのタワーからどのタワーへも隣接するタワーへ移動する操作を繰り返して移動できる．

最初，猫が高さ N のタワーの上にいる．

次に，キャットエクササイズを行う． キャットエクササイズとは，1 つのタワーを選んでそこに障害物を置く操作の繰り返しである． ただし，既に障害物を置いたタワーに再び障害物を置くことはできない． 操作によって以下のことが起こる．

• 選んだタワーに猫がいない場合，何も起こらない．
• 選んだタワーに猫がおり，かつそれに隣接するタワーすべてに障害物が置かれている場合，キャットエクササイズが終了する．
• いずれでもない場合，障害物が置かれていない隣接するタワーへの移動を繰り返して選んだタワーから移動できるタワーのうち，選んだタワーを除いて最も高いタワーへ，隣接するタワーへの移動を繰り返すことで猫が移動する．このとき，猫は隣接するタワーへの移動の回数が最小になるように移動する．

タワーの高さと隣接するタワーの組の情報が与えられたとき， 障害物の置き方を工夫したときの，猫が隣接するタワーへ移動する回数の合計の最大値を求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 200\,000．
• 1 \leqq P_i \leqq N (1 \leqq i \leqq N)．
• P_i \neq P_j (1 \leqq i < j \leqq N)．
• 1 \leqq A_j < B_j \leqq N (1 \leqq j \leqq N-1)．
• はじめ，どのタワーからどのタワーへも隣接するタワーへ移動する操作を繰り返して移動できる．
• 入力される値はすべて整数である．

小課題

• (7 点) A_i=i，B_i=i+1 (1 \leqq i \leqq N-1)，N \leqq 16．
• (7 点) A_i=i，B_i=i+1 (1 \leqq i \leqq N-1)，N \leqq 300．
• (7 点) A_i=i，B_i=i+1 (1 \leqq i \leqq N-1)，N \leqq 5\,000．
• (10 点) N \leqq 5\,000．
• (20 点) A_i=i，B_i=i+1 (1 \leqq i \leqq N-1)．
• (23 点) A_i=\left\lfloor \frac{i+1}{2} \right\rfloor，B_i=i+1 (1 \leqq i \leqq N-1)．ただし，\lfloor x \rfloor は x の小数点以下を切り捨てた値を表す．
• (26 点) 追加の制約はない．

入力例 1

4
3 4 1 2
1 2
2 3
3 4

出力例 1

3

以下のようにキャットエクササイズを行ったとき，猫は合計 3 回移動する．

• タワー 1 に障害物を置く．このとき，猫は移動しない．
• タワー 2 に障害物を置く．このとき，猫はタワー 2 からタワー 3 へ移動し，続いてタワー 3 からタワー 4 へと移動する．
• タワー 4 に障害物を置く．このとき，猫はタワー 4 からタワー 3 へと移動する．
• タワー 3 に障害物を置く．ここでキャットエクササイズが終了する．

猫が 4 回以上隣接するタワーへの移動を行うキャットエクササイズの方法は存在しないため，3 を出力する．

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

入力例 2

7
3 2 7 1 5 4 6
1 2
1 3
2 4
2 5
3 6
3 7

出力例 2

7

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

問題文

ビ太郎は，誕生日プレゼントとして JOI マシンをもらった． JOI マシンは，1 個の ボール，N 個の ライトタイル，M 個の ボタン からなる． ライトタイルにはそれぞれ 1 から N までの番号が付けられており， 電源を入れると，ライトタイル i (1 \leqq i \leqq N) は色 C_i (青 (B)，赤 (R) のいずれか) で光るようになっている． また，ボタンにはそれぞれ 1 から M までの番号が付けられており， ボタン j (1 \leqq j \leqq M) を押すと，次のようなことが起こる．

1. ライトタイル A_j の上にボールが置かれる．
2. ライトタイル A_j の色が (元の色にかかわらず) 赤になる．

3. ボールが取り除かれるまで，以下のことが繰り返し行われる．

   今，ボールが置かれているライトタイルの番号を p とする．

   ライトタイル p の色が青の場合

   ライトタイル p の色が赤に変わる．その後，もし p=1 の場合はボールが取り除かれ，そうでない場合はボールがライトタイル p-1 の上に移動する．

   ライトタイル p の色が赤の場合

   ライトタイル p の色が青に変わる．その後，もし p=N の場合はボールが取り除かれ，そうでない場合はボールがライトタイル p+1 の上に移動する．

JOI マシンに興味を持ったビ太郎は，Q 回の実験を計画している． k 回目 (1 \leqq k \leqq Q) の実験は，JOI マシンの電源を入れた後，ボタン L_k, L_k+1, \ldots, R_k をこの順に押すというものである． ただし，ボールが取り除かれるまでは，次のボタンを押さずに待つものとする．

JOI マシンの情報および実験の情報が与えられるので， それぞれの実験について，実験が終わった後における，色が赤であるようなライトタイルの個数を求めるプログラムを作成せよ．

制約

• 3 \leqq N \leqq 120\,000．
• 1 \leqq M \leqq 120\,000．
• C_i (1 \leqq i \leqq N) は B または R である．
• 1 \leqq A_j \leqq N (1 \leqq j \leqq M)．
• 1 \leqq Q \leqq 120\,000．
• 1 \leqq L_k \leqq R_k \leqq M (1 \leqq k \leqq Q)．
• N, M, A_j, Q, L_k, R_k は整数である．

小課題

• (3 点) N \leqq 300，M \leqq 300，Q = 1．
• (12 点) N \leqq 7\,000，M \leqq 7\,000，Q = 1．
• (10 点) Q \leqq 5．
• (11 点) N = 10，C_i は R である (1 \leqq i \leqq N)．
• (26 点) i \leqq t ならば C_i が R であり，i > t であれば C_i が B であるような整数 t (0 \leqq t \leqq N) が存在する．
• (17 点) A_j \leqq 20 または A_j > N - 20 (1 \leqq j \leqq M)．
• (21 点) 追加の制約はない．

入力例 1

5 1
RBRRB
4
1
1 1

出力例 1

1

1 回目の実験は次のように進行する．

1. ボタン 1 が押され，ボールがライトタイル 4 の上に置かれる．
2. ライトタイル 4 の色が赤になる．ただし，元からライトタイル 4 の色が赤なので，ライトタイル 4 の色は変わらない．
3. その後，次のことが起こる．
   1. 現在のライトタイル 4 の色は赤なので，ライトタイル 4 の色が青に変わり，ボールがライトタイル 5 の上に移動する．
   2. 現在のライトタイル 5 の色は青なので，ライトタイル 5 の色が赤に変わり，ボールがライトタイル 4 の上に移動する．
   3. 現在のライトタイル 4 の色は青なので，ライトタイル 4 の色が赤に変わり，ボールがライトタイル 3 の上に移動する．
   4. 現在のライトタイル 3 の色は赤なので，ライトタイル 3 の色が青に変わり，ボールがライトタイル 4 の上に移動する．
   5. 現在のライトタイル 4 の色は赤なので，ライトタイル 4 の色が青に変わり，ボールがライトタイル 5 の上に移動する．
   6. 現在のライトタイル 5 の色は赤なので，ライトタイル 5 の色が青に変わり，ボールが取り除かれる．

実験が終わった時点で，色が赤であるようなライトタイルはライトタイル 1 の 1 つのみであるため，1 を出力する．

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

入力例 2

5 3
RBRBR
1 3 4
2
2 3
1 3

出力例 2

5
0

1 回目の実験については，実験が終わった時点で，色が赤であるようなライトタイルはライトタイル 1, 2, 3, 4, 5 の 5 つであるため，5 を出力する．

2 回目の実験については，実験が終わった時点で，色が赤であるようなライトタイルは存在しないため，0 を出力する．

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

入力例 3

10 3
BBRRBRBRRB
2 10 5
1
1 3

出力例 3

2

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

入力例 4

10 10
RRRRRRRRRR
3 1 4 1 5 9 2 6 5 3
5
1 7
2 8
3 9
4 10
1 10

出力例 4

4
8
10
0
9

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

入力例 5

10 10
RRRBBBBBBB
3 1 4 1 5 9 2 6 5 3
5
1 10
2 9
3 8
4 7
5 6

出力例 5

2
6
0
10
7

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

入力例 6

30 10
RRRBBRBBBRBBBRBRBRRRRRBBBBRBRR
3 28 2 29 1 30 6 14 7 7
10
1 10
2 3
2 5
2 8
3 3
3 6
4 5
4 7
5 9
10 10

出力例 6

21
15
15
4
17
16
14
20
12
23

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