0285 - つらら (Icicles)

問題

　カナダに住む 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) が書かれている．
　採点用データのうち，配点の 30% 分については，N ≤ 500 かつ L ≤ 1000 を満たす．

出力

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

入出力例

入力例 1

4 6
4
2
3
5

出力例 1

8

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

入力例 2

6 10
3
4
1
9
5
1

出力例 2

15