問題文

JOI 君は明日から新たにソーシャルゲームを始めることにした．

このソーシャルゲームでは，1 日につき 1 回までログインすることができ，ログインするたびに A 枚のコインが得られる．

また，月曜日から日曜日まで 7 日連続でログインすると，そのたびに，追加で B 枚のコインが得られる．

これ以外にコインがもらえることはない．

明日は月曜日である．JOI 君が少なくとも C 枚のコインを得るためにログインしなければならない回数の最小値を求めよ．

制約

• 1 ≦ A ≦ 1000
• 0 ≦ B ≦ 1000
• 1 ≦ C ≦ 1000000 (= 10^6)

入力例 1

3 0 10

出力例 1

4

• 1 回のログインあたり 3 枚のコインが得られ，10 枚のコインを集めたい．
• JOI 君は，月曜日から連続 4 日間ログインすることで 12 枚のコインが得られる．
• 3 回以下のログインで 10 枚以上のコインを得ることはできないので，JOI 君がログインしなければならない回数の最小値は 4 である．従って，4 を出力する．

入力例 2

1 2 10

出力例 2

8

• 1 回のログインあたり 1 枚のコインが得られる．それとは別に，1 週間連続でログインすることで 2 枚のコインが得られる．10 枚のコインを集めたい．
• 月曜日から日曜日まで連続でログインすると，日々のコイン 7 枚に加えて，2 枚のコインが得られるため，合計 9 枚のコインが得られる．従って，更にもう 1 回ログインすることにより，10 枚のコインが得られる．
• 7 回以下のログインで 10 枚以上のコインを得ることはできないので，JOI 君がログインしなければならない回数の最小値は 8 である．従って，8 を出力する．

問題文

JOI 君はすごろくを持っている．このすごろくは 2019 個のマスが横一列に並んだ形をしている．これらのマスには，左端のスタートマスから右端のゴールマスへと順に 1 から 2019 までの番号がついている．

現在このすごろくの上には，N 個の駒が置かれている．これらの駒には，スタートに近い順に 1 から N までの番号がついている．駒 i (1 ≦ i ≦ N) は，マス X_i に置かれている．すべての駒は異なるマスに置かれている．

JOI 君はこれから M 回の操作を行う．j 回目 (1 ≦ j ≦ M) の操作では，駒 A_j を 1 マス先へ進める．ただし，移動元のマスがゴールマスであった場合，もしくは移動先のマスに別の駒が置かれている場合，駒 A_j は進まず，位置は変わらない．

すべての操作が終了した時点で，各駒が置かれているマスを求めよ．

制約

• 1 ≦ N ≦ 100
• 1 ≦ X_1 < X_2 < ... < X_N ≦ 2019
• 1 ≦ M ≦ 100
• 1 ≦ A_j ≦ N (1 ≦ j ≦ M)

入力例 1

3
2 3 6
2
1 3

出力例 1

2
3
7

1 回目の操作では，駒 1 をマス 2 からマス 3 へと進めようする．しかし，駒 2 がすでにマス 3 に置かれているため，駒 1 は進まない．

2 回目の操作では，駒 3 をマス 6 からマス 7 へと進める．

すべての操作が終了した時点で，駒 1 はマス 2 に，駒 2 はマス 3 に，駒 3 はマス 7 に置かれている．

入力例 2

2
1 2016
4
2 2 2 2

出力例 2

1
2019

3 回目の操作が完了した時点で，駒 2 はマス 2019 に置かれている．そのため，4 回目の操作では駒 2 は進まない．

入力例 3

4
1001 1002 1003 1004
7
1 2 3 4 3 2 1

出力例 3

1002
1003
1004
1005

問題文

JOI 君はマルスタンプ，バツスタンプ，マルバツスタンプの3種類のスタンプをそれぞれ 0 個以上持っている．これらはマルやバツのマークを紙に印字することができるスタンプである．

マルスタンプを使うとマルが 1 つ印字され，バツスタンプを使うとバツが 1 つ印字される．マルバツスタンプを使うとマルとバツが横一列に 1 つずつ印字され，スタンプの向きを変えることで，マルの右にバツが来るようにも，バツの右にマルが来るようにも印字できる．

JOI 君は，持っているスタンプをそれぞれちょうど 1 回ずつ適当な順番で使い，紙に横一列にマルとバツを印字した．印字されたマルとバツの列は文字列 S で表される．S は O と X から構成された長さ N の文字列であり，S_i = O ならば JOI 君が印字したマークのうち左から i 番目のものがマルであることを表し，S_i = X ならばそれがバツであることを表す (1 ≦ i ≦ N)．

あなたは，JOI 君が持っているスタンプの個数は分からないが，JOI 君が印字したマルとバツの列は知っている．印字されたマルとバツの列から，JOI 君が持っているマルバツスタンプの個数としてあり得るもののうち最大値を求めよ．

制約

• 1 ≦ N ≦ 100000 (= 10^5)
• S は長さ N の文字列である．
• S の各文字は O か X である．

入力例 1

5
OXXOX

出力例 1

2

JOI 君が印字したマークは，左から順に，マル，バツ，バツ，マル，バツである．JOI 君がマルスタンプ，バツスタンプ，マルバツスタンプをそれぞれ 0, 1, 2 個持っているとすると，以下の順番でスタンプを使えば，そのようにマークを印字することができる．

• 1 つ目のマルバツスタンプを使ってマルとバツをこの順に印字する．
• この右に，2 つ目のマルバツスタンプを使ってバツとマルをこの順に印字する．
• 最後に，この右に，バツスタンプを使ってバツを印字する．

マルバツスタンプを 3 個以上持っているケースは考えられないので，2 を出力する．

入力例 2

14
OXOXOXOXXOXOXO

出力例 2

7

入力例 3

10
OOOOOOOOOO

出力例 3

0

問題文

日本列島は細長い列島である．日本列島は平行な境界線により N 個の区画に分けられている．区画には端から順に 1 から N の番号が付けられている．区画 i (1 ≦ i ≦ N) の高さは A_i である．

日本列島は海に囲まれており，海面の高さは場所によらず一定である．高さが海面の高さより高い区画を陸地と呼ぶ．

陸地が連続している部分のことを島と呼ぶ．より正確に書くと以下の通りである．整数 l, r (1 ≦ l ≦ r ≦ N) について，日本列島のうち区画 l，区画 l+1，...，区画 r からなる部分を領域 [l, r] という．以下の条件を満たす領域 [l, r] を島という：

• 区画 l，区画 l+1，...，区画 r はすべて陸地である．
• l>1 ならば区画 l-1 は陸地ではない．
• r<N ならば区画 r+1 は陸地ではない．

海面の上昇により，日本列島は少しずつ沈没している．現在の海面の高さは 0 であるが，これは時間が経つにつれて徐々に上がり，ついには日本全体が海になってしまう．

JOI 君は，海面の高さが上昇すると，日本の島の数が増減することに気付いた．現在から，日本に陸地がなくなるまでの間 (現在も含む) における，島の数の最大値を求めたい．

制約

• 1 ≦ N ≦ 100000 (= 10^5)
• 0 ≦ A_i ≦ 1000000000 (= 10^9) (1 ≦ i ≦ N)

入力例 1

6
0 1 2 1 3 2

出力例 1

2

• 海面の高さが 0 以上 1 未満のとき，区画 2, 3, 4, 5, 6 が陸地である．領域 [2, 6] が唯一の島なので，島の数は 1 である．
• 海面の高さが 1 以上 2 未満のとき，区画 3, 5, 6 が陸地である．領域 [3, 3] と領域 [5, 6] が島なので，島の数は 2 である．
• 海面の高さが 2 以上 3 未満のとき，区画 5 のみが陸地である．領域 [5, 5] が唯一の島なので，島の数は 1 である．
• 海面の高さが 3 になると，陸地はなくなり，島の数は 0 になる．

よって島の数の最大値は 2 なので，2 を出力する．

入力例 2

6
3 2 3 0 2 0

出力例 2

2

• 海面の高さが 0 以上 2 未満のとき，区画 1, 2, 3, 5 が陸地である．領域 [1, 3] と領域 [5, 5] が島なので，島の数は 2 である．
• 海面の高さが 2 以上 3 未満のとき，区画 1, 3 が陸地である．領域 [1, 1] と領域 [3, 3] が島なので，島の数は 2 である．
• 海面の高さが 3 になると，陸地はなくなり，島の数は 0 になる．

よって島の数の最大値は 2 なので，2 を出力する．

入力例 3

10
4 1 2 1 2 3 5 4 3 2

出力例 3

3

問題文

JOI 氏は，自宅の敷地に N 本の木を所有している．これらの木は一列に並んでおり，順に 1 から N までの整数で番号が付けられている．

この冬，JOI 氏はいくつかの木を選んで，イルミネーションを飾り付けることにした．イルミネーションには美しさと呼ばれる値が定まっている．木 i にイルミネーションを飾り付ける場合の美しさは A_i である．

JOI 氏は，あまりに近い 2 つの木の両方にイルミネーションを飾り付けてしまうと，眩しすぎる場合があることに気がついた．具体的には，j = 1, 2, ..., M に対して，木 L_j, L_j + 1, ..., R_j のうち 2 つ以上にイルミネーションを飾り付けるべきではないということが判明した．

この条件に従ってイルミネーションを飾り付けるときの，美しさの合計の最大値を求めよ．

制約

• 1 ≦ N ≦ 200000 (= 2×10^5)
• 1 ≦ M ≦ 200000 (= 2×10^5)
• 1 ≦ A_i ≦ 1000000000 (= 10^9) (1 ≦ i ≦ N)
• 1 ≦ L_j ≦ R_j ≦ N (1 ≦ j ≦ M)

入力例 1

4 1
1 2 3 8
2 4

出力例 1

9

この入力例では，木 1, 4 にイルミネーションを飾り付けると，美しさの合計が 9 となり最大となる．L_1 = 2, R_1 = 4 なので，木 2, 3, 4 のうち 2 つ以上にイルミネーションを飾り付けることはできない．例えば木 1, 2, 4 にイルミネーションを飾り付けることはできないことに注意せよ．

入力例 2

5 2
2 3 9 5 6
1 3
2 4

出力例 2

15

入力例 3

20 10
870851814 594414687 615919461 65033245 460143082 617460823 881870957 126041265 623075703 34130727 27054628 853567651 483228744 491145755 220689940 148007930 229257101 790404982 612186806 281076231
15 19
20 20
12 13
1 4
19 19
9 13
3 6
9 12
16 16
18 19

出力例 3

4912419478

問題文

2XXX 年，世界の国は直線状に並んでいた．N 個の国があり，1, 2, ..., N の番号が付けられている．i = 1, 2, ..., N - 1 に対し，国 i と国 i + 1 が互いに隣国である．

この年の国際情報オリンピックでは，国 i からは A_i 人の選手が参加する．国際情報オリンピックの技術委員のあなたは，競技での座席表を作成する担当である．競技会場が細長いため，一列に並んだ A_1 + A_2 + ... + A_N 個の座席に選手たちを割り当てることになった．不正防止のため，同じ国の選手や隣国の選手を隣り合う席に割り当ててはならない．

選手たちを座席に割り当てる方法は何通りあるだろうか．この数は非常に大きくなる可能性があるので，それを 10007 で割った余りを求めたい．

制約

• 1 ≦ N ≦ 100
• 1 ≦ A_i ≦ 4 (1 ≦ i ≦ N)

入力例 1

4
2 1 1 1

出力例 1

4

国 1 から参加する 2 人の選手を 1 と 1'，国 2 から参加する 1 人の選手を 2，国 3 から参加する 1 人の選手を 3，国 4 から参加する 1 人の選手を 4 で表すことにすると，選手たちを座席に割り当てる方法としては，以下の 4 通りの並べ方が考えられる：

• 1, 3, 1', 4, 2
• 1', 3, 1, 4, 2
• 2, 4, 1, 3, 1'
• 2, 4, 1', 3, 1

入力例 2

5
1 2 3 2 1

出力例 2

0

この入力例では，条件を満たす座席表は存在しない．

入力例 3

6
1 2 3 3 2 1

出力例 3

4754

この入力例では，選手たちを座席に割り当てる方法は 24768 通りあるため，それを 10007 で割った余りである 4754 を出力する．