Icicles

Time Limit : 8 sec, Memory Limit : 65536 KB

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

つらら

問題

カナダに住む JOI 君の家の軒下には,立派なつららが出来ている.せっかくなの で,JOI 君はつららについて調べてみることにした.

JOI 君の家の軒下には N 本(2 ≤ N ≤ 100000 = 105 )のつららが出来ている.こ れらのつららは一直線上に並んでおり,軒下の左端から i cm(1 ≤ i ≤ N )の位置 に i 本目のつららが出来ている.i 本目のつららの長さは最初 ai cm(ai は 1 以上の 整数)である.これらのつららは,次のような規則によって伸びていく:

  • i 本目のつららは,i − 1 本目のつららと i + 1 本目のつららの両方よりも長い場 合にのみ,1 時間につき 1 cm ずつ伸びる(ただし,両端のつららに関しては 片方の隣のみ考える.すなわち,1 本目のつららは 2 本目のつららより長けれ ば伸び,N 本目のつららは N − 1 本目のつららより長ければ伸びる).
  • どのつららも,L cm(2 ≤ L ≤ 50000)に達した瞬間に,根元から折れる(折 れたつららは,以後長さ 0 cm のつららとみなす) .

最初の段階で,隣り合う 2 本のつららの長さはすべて異なっている.このとき,十分 な時間が経過すれば,N 本すべてのつららが折れて長さ 0 cm となる.JOI 君は,つ ららがこのような状態になるまでの時間を知りたくなった.

N 本のつららの最初の長さとつららの限界の長さ L が与えられると,すべてのつ ららが折れるまでにかかる時間を求めるプログラムを作成せよ.

入力

入力ファイルのファイル名は input.txt である.

入力の 1 行目には,つららの本数を表す整数 N とつららの限界の長さを表す整数 L が,空白を区切りとしてこの順に書かれている.入力の i + 1 行目 (1 ≤ i ≤ N) に は, i 本目のつららの最初の長さを表す整数 ai (1 ≤ ai < L) が書かれている.

採点用データのうち,配点の 30% 分については,N ≤ 500 かつ L ≤ 1000 を満 たす.

出力

出力ファイルのファイル名は output.txt である.

output.txt は,すべてのつららが折れるまでにかかる時間を表す 1 つの整数のみ を含む 1 行からなる.

入出力例

入力例 1
4 6
4
2
3
5
  
 
出力例 1
8
   
入力例 2
6 10
3
4
1
9
5
1
  
 
出力例 2
15
   

例 1 の場合,1, 2, 3, 4 本目のつららは,それぞれ 2, 8, 4, 1 時間後に折れる.した がって,すべてのつららが折れるまでにかかる時間は 8 時間であるので,8 を出力 する.

Notes on Submission

標準入出力を行うプログラムを作成して下さい.


Source: 9th Japanese Olympiad in Informatics , 2010-02-14
http://www.ioi-jp.org/