암소 배시는 그녀의 육중한 체중이 봅슬레이 경기에 이점이 있어 L (2 <= L <= 1,000,000,000) 미터 코스의 경기에 출전하려고 한다.
경기의 시작 라인에서 초당 1 미터의 속도로 시작을 하지만 경기동안 속도를 변경할 수가 있다.
경기를 할 동안 세 가지 형태의 속도를 낼수 가 있다.
베시는 N (1 <= N <= 100,000)개의 턴 지점이 있어 이 지점 T_i (1 <= T_i <= L-1) 에서는 안전을 고려하여 S_i (1 <= S_i <= 1,000,000,000)속도 이하를 유지하려고 한다.
베시를 도와 이 조건을 만족하면서 얻을 수 있는 최대 속도를 구하여야 한다.
예시로 주어진 데이터에서의 코스이고 [] 안의 숫자는 그 지점에서의 제한 속도이다.
| 1 2 3 4 5 6 7[3]
|---+---+---+---+---+---+---+
| \
Start + 8
\
+ 9
\
+ 10 +++ 14 (finish)
\ /
11[1] +---+---+
12 13[8]
아래는 위 코스에서 최대 속도를 내기 위한 거리와 속도 표이다.
Max: 3 1 8 Mtrs: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Spd: 1 2 3 4 5 5 4 3 4 3 2 1 2 3 4
이 경우 최대 속도는 5 이다.
입력 14 3 7 3 11 1 13 8 출력 5
출처:usaco 2009 silver