Problems
처마 끝에 N개의 고드름이 일렬로 달려있다.
왼쪽에서부터 i번째 고드름은 A_i센티미터이다.
각각의 고드름은 자기 바로 옆에 자신보다 긴 고드름이 없으면 1시간 뒤 1센치만큼 자란다.
한 고드름이 계속 자라 L센치가 되면 그 즉시 부러져 떨어지고 만다.
부러진 고드름은 0cm가 되었다고 간주하면 되며, 다시 자라지 않는다.
처음에는 모든 인접한 고드름의 길이가 서로 다르고 1이상 L미만의 길이로 달려있다.
이 경우 시간이 충분히 지나면 어느 순간 모든 고드름이 부러져 0cm가 된다.
이때는 과연 몇 시간이 지난 시점일까?
Input
첫 줄에 N, L이 주어진다.
이후 N줄에 걸쳐 i번째 줄에는 A_i가 주어진다.
2 <= N <= 100000
2 <= L <= 50000
1 <= A_i < L
Output
모든 고드름이 부러지는데 걸리는 시간을 출력하라.
Example #1
4 6
4
2
3
5
8
Example #2
6 10
3
4
1
9
5
1
15
Source
JOI 2010
You must sign in to write code.