시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 128 MB 388 116 (30%) 104
문제
$N$개의 풍선이 큰 방의 왼쪽부터 오른쪽까지 한 줄로 떠있다. 소년 Perica는 활을 가지고 놀며 사냥연습을 하는 것을 좋아한다. 그는 그가 고른 임의의 높이에서 방의 왼쪽에서 오른쪽으로 활을 쏜다. 화살은 선택된 높이 $H$에서 왼쪽부터 오른쪽으로 풍선을 만날때까지 날아가는데 풍선을 만나게 되면 풍선은 터지고 화살은 높이가 $1$만큼 감소하게 된다. 즉 만약 화살이 높이 $H$에서 날다가 풍선을 터뜨리면 높이 $H-1$에서 날게 되는 것이다. 우리의 영웅의 목표는 풍선을 최대한 적은 화살을 사용하여 모두 터뜨리는 것이다.
입력
첫째 줄에는 $N(1 ≤ N ≤ 1,000,000)$이 주어진다. 둘째 줄에는 $N$개의 정수 $H_i$가 주어진다. 각 $H_i(1 ≤ H_i ≤ 1,000,000)$는 $i$번째 풍선의 높이이고 각각 왼쪽부터 오른쪽으로 나열된 순서로 주어진다.
출력
첫째 줄에 Pero가 풍선을 모두 터뜨리기 위해 필요한 화살의 최소 개수를 출력하라.
힌트
#### 점수 40%에 경우에 $N ≤ 5,000$이다. #### 예제 입력 1 ``` 5 2 1 5 4 3 ``` #### 예제 출력 1 ``` 2 ``` #### 예제 입력 2 ``` 5 1 2 3 4 5 ``` #### 예제 출력 2 ``` 5 ``` #### 예제 입력 3 ``` 5 4 5 2 1 4 ``` #### 예제 출력 3 ``` 3 ``` #### 예제 설명 1 높이 5에서 화살을 쏘면 [5, 4, 3]이 터지고 높이 2에서 화살을 쏘면 [2, 1]이 터지게 된다.