문제
큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다.
수완이는 화살 가지고 사냥 연습하는 것을 좋아한다. 수환이는 임의의 높이에서 화살을 왼쪽에서 오른쪽으로 쏜다.
화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다.
화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다.
화살은 계속해서 진행해 가는데 높이는 1 줄어든다.
따라서 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.
수완이는 모든 풍선을 터트리되 가능한 적은 수의 화살을 사용하고자 한다.
수완이를 도와 가장 적은 수의 화살 개수를 구해보자.
입력
첫 번째 줄에는 풍선의 개수 정수 N(1 ≤ N ≤ 1,000,000)이 입력된다.
두 번째 줄에는 각 풍선의 높이 Hi가 공백으로 구분하여 입력된다.
각각의 Hi(1 ≤ Hi ≤ 1,000,000)는 i번째 풍선의 높이에 해당하며 왼쪽에서 오른쪽으로 나열되는 순서이다.
출력
첫 행에 필요한 화살 개수의 최소값을 출력한다.
예제1
입력
5
21543
출력
2
예제2
입력
5
12345
출력
5
예제3
입력
5
45214
출력
3
출처
COCI 2015/2016 contest1 3