#1516 고드름

20  10 s   128 MB  

Description

 

 캐나다에 사는 타블로의 집처마밑에 거대한 고드름이 생겼다. 드문 기회이기 때문에, 타블로는 고드름을 조사해 보기로 했다.

 타블로의 집처마 밑에는 N개 ( 2≤N≤100,000)의 고드름이 생겼다.

이 고드름들은 일직선위에 늘어서 있고 처마밑의 왼쪽부터 i cm (1≤i≤N )의 위치에 i개의 고드름이 있다.

i개의 고드름의 길이는 처음에 ai cm (ai 는 1이상의 정수)이다. 이 고드름들은 다음 규칙들에 따라 자라난다.

 

 

 처음 상태에선 이웃한 2개의 고드름의 길이는 모두 다르게 되어있다. 이 경우에 충분한 시간이 경과하면 N개의 고드름이 모두 부러져서 길이가 0cm가 된다. 타블로는 고드름이 이와 같은 상태가 될때까지의 시간을 알고싶다.

 N개의 고드름이 최초의 길이와 고드름의 한계길이가 주어졌을때 모든 고드름이 부러질때까지 걸린 시간을 구하는 프로그램을 작성하여라.

Input

 입력의 1행에는 고드름이 몇개가 있는지를 나타내는 정수 N과 고드름의 한계길이를 나타내는 정수 L이 공백으로 구분되어서 써있다. 입력의 i+1행에는 (1≤i≤N), i번째 고드름의 최초의 길이를 나타내는 정수 ai (1≤ai≤L)가 써있다.

Output

모든 고드름이 부러질 때까지 걸린 시간을 나타내는 정수를 한줄에 출력한다.

Sample Input

Sample Output

4 6
4
2
3
5
8

HINT

또 다른 예시

Sample Input

6 10
3
4
1
9
5
1

Sample Output

15

첫번째 예시의 경우, 1,2,3,4번째 의 고드름이 각각 2,8,4,1 시간에 부러진다. 따라서 고드름이 모두 부러질때까지 걸린 시간은 8시간이 되기때문에 8을 출력한다.

Source

Japan Olympiad in Informatics 2009-2010