농부 존은 그의 목초지에 일렬로 서 있는 N (1 <= N <= 50,000) 그루의 나무 그루터기를 없애고자 한다. 각 나무는 순차적으로 1 , 2 , 3 .. , n 으로 번호가 부여되어 있고 , 각 높이 Hi (1 <= H_i <= 10,000)이다.
그는 고성능 화약을 이용해서 나무를 쓰러뜨리는데 , 이 폭발은 강력해서 인접한 나무들을 동시에 쓰러뜨릴 수 있다. 단 , 쓰러진 나무 좌우에 있는 나무의 높이가 쓰러진 나무보다 높이가 작은 경우에...(도미노 씩으로)
예를 들어 아래와 같이 나무의 높이가 주어지는 경우
1 2 5 4 3 3 6 6 2높이 5 인 세 번째 나무를 쓰러뜨리면 왼쪽 2 가 넘어가고 , 다음 1 이 넘어간다. 마찬가지로 우측에서는 4 , 3 이 차례대로 넘어간다.
남은 나무는
* * * * * 3 6 6 2이고 , 7 번째 나무 , 8 번째 나무를 쓰러뜨리면 모든 나무를 쓰러뜨릴수 있다.
입력 9 1 2 5 4 3 3 6 6 2 출력 3 7 8
출처: USACO 2006 January Bronze