5562번 - つらら 다국어

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

JOI 君の家の軒下には N 本（2 ≤ N ≤ 100000 = 10⁵）のつららが出来ている．こ れらのつららは一直線上に並んでおり，軒下の左端から i cm（1 ≤ i ≤ N）の位置 に i 本目のつららが出来ている．i 本目のつららの長さは最初 a_i cm（a_i は 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 が与えられると，すべてのつ ららが折れるまでにかかる時間を求めるプログラムを作成せよ．

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

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

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