家庭菜園が趣味のビ太郎は自宅の庭でビバ草という植物を育てている．庭には N 株のビバ草が東西方向に一列に植えられており，西側から順に 1 から N までの番号が付いている．現在，ビバ草 i (1 \leqq i \leqq N) の背丈は A_i である．

育てているビバ草は特別な品種改良の結果，水を与えるたびに背丈が 1 伸びる．ビ太郎は庭の見栄えを良くするために水やりを複数回行い，以下の条件を満たすようにしたいと考えている．

• すべての水やりを行った後のビバ草 i (1 \leqq i \leqq N) の背丈を B_i とする．このとき，「1 \leqq j \leqq k - 1 に対し B_j < B_{j + 1}」かつ「k \leqq j \leqq N - 1 に対し B_j > B_{j + 1}」を満たすような整数 k (1 \leqq k \leqq N) が存在する．

ただし，ビ太郎は不器用なため，1 回の水やりにおいて，ある区間上のビバ草に一斉に水を与えることしかできない．すなわち，水やりを行うたびにある整数 L, R (1 \leqq L \leqq R \leqq N) を選び，ビバ草 L, L + 1, \ldots, R に水を与える．

ビ太郎は水やりの回数をできるだけ少なくしたい．

ビバ草の数と現在の背丈の情報が与えられたとき，条件を満たすのに必要な水やりの回数の最小値を求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 200\,000．
• 1 \leqq A_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．

小課題

1. (40 点) N \leqq 2\,000．
2. (60 点) 追加の制約はない．

入力例 1

5
3 2 2 3 1

出力例 1

3

以下のように水やりを 3 回行うことで条件を満たすことができる．

• L=2，R=5 として，ビバ草 2, 3, 4, 5 に水を与える．ビバ草の背丈は西から順に 3, 3, 3, 4, 2 となる．
• L=2，R=3 として，ビバ草 2, 3 に水を与える．ビバ草の背丈は西から順に 3, 4, 4, 4, 2 となる．
• L=3，R=3 として，ビバ草 3 に水を与える．ビバ草の背丈は西から順に 3, 4, 5, 4, 2 となる．

2 回以下の水やりで条件を満たすことは不可能なので，必要な水やりの回数の最小値は 3 である．

入力例 2

5
9 7 5 3 1

出力例 2

0

すでに条件を満たしているため，必要な水やりの回数の最小値は 0 である．

入力例 3

2
2021 2021

出力例 3

1

1 回の水やりで条件を満たすためには，L = 1，R = 1 としてビバ草 1 に水を与えるか，または，L = 2，R = 2 としてビバ草 2 に水を与えればよい．

入力例 4

8
12 2 34 85 4 91 29 85

出力例 4

93

JOI 平原は東西方向に広がるとても大きな平原である．この平原は数直線と見なすことができ，各地点は東向きを正とする座標であらわされる．JOI 平原は冬を迎え N 個の雪玉が異なる座標に作られた．雪玉には西から順に 1 から N までの番号が付いている．最初，雪玉 i (1 \leqq i \leqq N) の座標は整数 X_i であった．

また JOI 平原は冬に強い風が吹くことで知られている．あなたは Q 日間の風の観測データを入手した．j 日目 (1 \leqq j \leqq Q) の風のデータは整数 W_j であらわされる．W_j が負のときは西向きに，W_j が負でないときは東向きに，強さ \lvert W_j \rvert の風が吹いたことを意味する．

風が吹くと，雪玉は風と同じ向きに，風の強さと同じ距離だけ転がる．すなわち j 日目 (1 \leqq j \leqq Q) の始めに座標 x に雪玉があったとき，その雪玉は座標 x から座標 x + W_j まで転がる．j 日目の終わりには，その雪玉の座標は x + W_j になる．ただし，各日においてすべての雪玉が同時に，同じ速さで転がる．

最初，JOI 平原全体に雪が積もっていた．雪が積もっている範囲を雪玉が転がると，雪が付着し，雪玉の重さが増え，その範囲の雪はなくなる．すなわち，aを整数とし，座標 a から座標 a + 1 までの範囲に雪が残っているとする．このとき，雪玉がこの範囲を転がると，その雪玉の重さが 1 増えて，座標 a から座標 a + 1 までの範囲の雪がなくなる．ただし，雪が残っていない範囲を雪玉が転がったとしても，雪玉の重さは変わらない．

最初，すべての雪玉の重さは 0 であった．また，観測した Q 日間に新たに雪は降らなかった．

あなたは Q 日目の終わりにおける雪玉の重さを知りたい．

雪玉の最初の座標，Q 日間の風の観測データが与えられたとき，Q 日目の終わりにおける，それぞれの雪玉の重さを求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 200\,000．
• 1 \leqq Q \leqq 200\,000．
• \lvert X_i \rvert \leqq 1\,000\,000\,000\,000 \ (= 10^{12}) (1 \leqq i \leqq N)．
• X_i < X_{i + 1} (1 \leqq i \leqq N - 1)．
• \lvert W_j \rvert \leqq 1\,000\,000\,000\,000 \ (= 10^{12}) (1 \leqq j \leqq Q)．

小課題

1. (33 点) N \leqq 2\,000，Q \leqq 2\,000．
2. (67 点) 追加の制約はない．

入力例 1

4 3
-2 3 5 8
2
-4
7

出力例 1

5
4
2
6

この入力例では，雪玉の座標と重さは以下のように変化する．

• 最初，各雪玉の座標は，雪玉 1 から順に -2, 3, 5, 8 である．各雪玉の重さは，雪玉 1 から順に 0, 0, 0, 0 である．
• 1 日目には東向きに強さ 2 の風が吹く．1 日目の終わりにおける，各雪玉の座標は，雪玉 1 から順に 0, 5, 7, 10 である．各雪玉の重さは，雪玉 1 から順に 2, 2, 2, 2 である．
• 2 日目には西向きに強さ 4 の風が吹く．2 日目の終わりにおける，各雪玉の座標は，雪玉 1 から順に -4, 1, 3, 6 である．各雪玉の重さは，雪玉 1 から順に 4, 4, 2, 3 である．
• 3 日目には東向きに強さ 7 の風が吹く．3 日目の終わりにおける，各雪玉の座標は，雪玉 1 から順に 3, 8, 10, 13 である．各雪玉の重さは，雪玉 1 から順に 5, 4, 2, 6 である．

よって3 日目の終わりにおける，各雪玉の重さ 5, 4, 2, 6 を順に出力する．

入力例 2

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

出力例 2

3000000000000

入力例 3

10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6

出力例 3

14
8
7
9
11
10
9
8
5
10

とある合宿の最終日，合宿の参加者 N 人で集合写真を撮ることとなった．参加者には身長の低い順に 1 から N までの番号が付けられている．参加者 h の身長は h である (1 \leqq h \leqq N)．

集合写真は，階段の上に並んで撮影する．この階段はちょうど N 段からなり，低い方から順に 1 から N までの番号が付けられている．段 i + 1 は段 i よりもちょうど 2 だけ高い (1 \leqq i \leqq N - 1)．階段の幅はとても狭いため，それぞれの段に参加者が 1 人ずつ立って，縦一列に並んで撮影する．

間もなく撮影が行われようとしており，それぞれの段に参加者が立っている．現在，段 i (1 \leqq i \leqq N) に立っている参加者は，参加者 H_i である．

ところが，あまりにも参加者の身長が違いすぎるため，この並び順では写真に写らない参加者がいるかもしれない．そこで，あなたは参加者の位置を並べ替えて，少なくとも全員の頭の上部が写るようにしたい．すなわち，次の条件が満たされるようにしたい．

• 段 i (1 \leqq i \leqq N) に立っている参加者の身長を a_i とする． このとき，すべての i (1 \leqq i \leqq N - 1) に対し，a_{i} < a_{i + 1} + 2 が成り立つ．

ただし，あなたは隣り合う参加者の位置を入れ替えることしかできない．すなわち，1 回の操作において，段 i (1 \leqq i \leqq N - 1) を任意に一つ選び，段 i の参加者と段 i + 1 の参加者を入れ替えることができる．

この操作をできるだけ少ない回数行うことで，条件が満たされるようにしたい．

現在の参加者の並び順が与えられたとき，必要な操作回数の最小値を求めるプログラムを作成せよ．

制約

• 3 \leqq N \leqq 5\,000．
• 1 \leqq H_i \leqq N (1 \leqq i \leqq N)．
• H_i \neq H_j (1 \leqq i < j \leqq N)．

小課題

1. (5 点) N \leqq 9．
2. (7 点) N \leqq 20．
3. (32 点) N \leqq 200．
4. (20 点) N \leqq 800．
5. (36 点) 追加の制約はない．

入力例 1

5
3 5 2 4 1

出力例 1

3

以下のように操作を 3 回行うことで，条件を満たすようにできる．

• まず，段 2 の参加者と段 3 の参加者を入れ替える．参加者の身長は前から順に 3, 2, 5, 4, 1 となる．
• 次に，段 4 の参加者と段 5 の参加者を入れ替える．参加者の身長は前から順に 3, 2, 5, 1, 4 となる．
• 最後に，段 3 の参加者と段 4 の参加者を入れ替える．参加者の身長は前から順に 3, 2, 1, 5, 4 となり，条件を満たす．

2 回以下の操作で条件を満たす状態にすることはできないので，3 を出力する．

入力例 2

5
3 2 1 5 4

出力例 2

0

すでに条件を満たしているので，操作を行う必要はない．

入力例 3

9
6 1 3 4 9 5 7 8 2

出力例 3

9

IOI 町には N 個の交差点があり，1 から N までの番号が付いている．また，M 本の道があり，1 から M までの番号が付いている．それぞれの道は 2 個の異なる交差点を双方向に結んでいる．道 i (1 \leqq i \leqq M) は交差点 A_i と交差点 B_i を結んでいる．2 本の異なる道が同じ交差点の組を結ぶことはない．これらの道には 1 以上 M 以下の整数で表される色が塗られており，道 i の現在の色は C_i である．複数の道が同じ色で塗られているかもしれない．

JOI 社は IOI 町の交差点を移動するロボットを開発した．あなたがこのロボットに道の色を指示すると，ロボットは指示された色の道を通り隣接した交差点に移動する．ただし，ロボットが現在いる交差点につながれた道のうちに，指示された色の道が 2 本以上存在すると，次に進むべき道を判別できずに停止してしまう．

あなたの目的は，現在交差点 1 にいるロボットに何回かの指示を出して，交差点 N に移動させることである．ただし，現在の道の色ではそれができるとは限らないため，何本かの道の色を事前に塗り替えることで， ロボットを交差点 N に移動させることができるようにしたい．道 i (1 \leqq i \leqq M) は P_i 円をかけて，1 以上 M 以下の好きな整数の色に塗り替えることが出来る．

交差点と道の情報が与えられたとき，必要な金額の最小値を求めるプログラムを作成せよ．ただし，どのように道の色を塗り替えてもロボットを交差点 N に移動させることができない場合は，代わりに -1 を出力せよ．

制約

• 2 \leqq N \leqq 100\,000．
• 1 \leqq M \leqq 200\,000．
• 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M)．
• (A_i, B_i) \neq (A_j, B_j) (1 \leqq i < j \leqq M)．
• 1 \leqq C_i \leqq M (1 \leqq i \leqq M)．
• 1 \leqq P_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq M)．

小課題

1. (34 点) N \leqq 1\,000，M \leqq 2\,000．
2. (24 点) P_i = 1 (1 \leqq i \leqq M)．
3. (42 点) 追加の制約はない．

入力例 1

4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2

出力例 1

3

1 円で道 4 を色 3 から色 4 に塗り替え，2 円で道 6 を色 4 から色 2 に塗り替える．合計 3 円かかる．

この結果，交差点 1 にいるロボットに色 2 を指示することで，ロボットを交差点 2 に移動させることができる．続けて，ロボットに色 4 を指示することで，ロボットを交差点 4 に移動させることができる．

2 円以下でロボットを交差点 4 に移動させることは不可能であるため，3 を出力する．

入力例 2

5 2
1 4 1 2
3 5 1 4

出力例 2

-1

道をどのように塗り替えても，ロボットを交差点 5 に移動させることはできない．したがって，-1 を出力する．

入力例 3

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

出力例 3

1

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

入力例 4

13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20

出力例 4

7

N+1 層からなるダンジョンがあり，ダンジョン内には M 人のプレイヤーがいる．ダンジョンの階層には入口から近い順に第 1 層から第 N+1 層までの番号が付いている．また，プレイヤーには 1 から M までの番号が付いている．

ダンジョンのある階層から次の階層へ進むには体力を要する．プレイヤーは，第 i 層 (1 \leqq i \leqq N) から第 i + 1 層に進む際に体力を A_i 消費する．また，このダンジョンは一方通行であり，可能な階層間の移動は第 i 層 (1 \leqq i \leqq N) から第 i + 1 層への移動のみである．

第 1 層から第 N 層までの各階層には 1 つの回復の泉がある．第 i 層 (1 \leqq i \leqq N) にある回復の泉では，プレイヤーは B_i 枚のコインを消費することで体力を 1 回復させることができる．回復の泉は，コインがある限り何回でも使用することができる．ただし，プレイヤーの体力には上限があり，回復の泉を使っても，体力がその上限を超えることはない．

プレイヤー j (1 \leqq j \leqq M) は現在第 S_j 層にいる．現在の体力は 0 であり，体力の上限は U_j である．プレイヤー j は，体力を 0 未満にすることなく第 T_j 層まで進もうとしている．そのためには何枚のコインが必要であろうか．

ダンジョンの情報と各プレイヤーの情報が与えられたとき，各プレイヤーが体力を 0 未満にせずに目標の階層まで進むことが可能かを判定し，可能な場合には必要なコインの枚数の最小値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 200\,000．
• 1 \leqq M \leqq 200\,000．
• 1 \leqq A_i \leqq 200\,000 (1 \leqq i \leqq N)．
• 1 \leqq B_i \leqq 200\,000 (1 \leqq i \leqq N)．
• 1 \leqq S_j < T_j \leqq N+1 (1 \leqq j \leqq M)．
• 1 \leqq U_j \leqq 100\,000\,000 (1 \leqq j \leqq M)．

小課題

1. (11 点) N \leqq 3\,000，M \leqq 3\,000．
2. (14 点) U_1 = U_2 = \cdots = U_M．
3. (31 点) T_j = N+1 (1 \leqq j \leqq M)．
4. (44 点) 追加の制約はない．

入力例 1

5 4
3 4 1 1 4
2 5 1 2 1
1 6 3
1 6 4
3 5 1
2 5 9

出力例 1

-1
29
3
22

プレイヤー 1 は，体力の上限が 3 であるため，第 2 層から第 3 層へ進むことができない．そのため，1 行目の出力は -1 となる．

一方で，プレイヤー 2 は体力の上限が 4 であるため，以下のようにして第 6 層まで進むことができる．

• 第 1 層でコインを 8 枚使って体力を 4 にし，第 2 層に進む．このとき，体力は 1 となる．
• 第 2 層でコインを 15 枚使って体力を 4 にし，第 3 層に進む．このとき，体力は 0 となる．
• 第 3 層でコインを 4 枚使って体力を 4 にし，第 4 層に進む．このとき，体力は 3 となる．
• 第 4 層ではコインを使わずに，第 5 層に進む．このとき，体力は 2 となる．
• 第 5 層でコインを 2 枚使って体力を 4 にし，第 6 層に進む．このとき，体力は 0 となる．

合計 29 枚のコインを使う．29 枚未満のコインで第 6 層まで進むことはできないので，2 行目の出力は 29 となる．

入力例 2

10 10
1 8 9 8 1 5 7 10 6 6
10 10 2 8 10 3 9 8 3 7
2 11 28
5 11 28
7 11 28
1 11 18
3 11 18
8 11 18
4 11 11
6 11 11
10 11 11
9 11 5

出力例 2

208
112
179
248
158
116
234
162
42
-1

この入力例は小課題 3 の制約を満たしている．

入力例 3

20 20
2 3 2 11 4 6 9 15 17 14 8 17 3 12 20 4 19 8 4 5
19 3 18 2 13 7 5 19 10 1 12 8 1 15 20 1 13 2 18 6
12 15 67
7 15 18
16 17 14
9 21 97
1 19 43
3 18 31
16 20 70
7 20 28
1 16 61
3 5 69
9 10 15
2 13 134
11 19 23
16 20 14
5 21 16
15 20 11
7 11 54
7 16 16
13 17 10
3 15 135

出力例 3

151
591
4
284
339
517
35
581
254
58
-1
178
519
-1
-1
-1
219
-1
-1
214