문제
여러분은 "곰돌이 푸"가 여자였다는 사실을 아셨나요? 저는 방금 처음 알았습니다.
곰돌이 푸는 꿀을 꿀단지에 모으는 취미를 갖고 있다.
푸의 남자친구 생일이 곧 다가오기에, 선물로 N개의 꿀단지를 준비하려 한다.
속이 빈 꿀단지를 선물하기는 좀 그래서, i번째 꿀단지에는 Ai만큼의 꿀을 채워넣으려 한다.
푸는 엄연히 곰이기 때문에, 꿀을 일일이 채우는 것이 귀찮다.
대신 어떤 구간 l~r을 잡아, 해당 구간 안에 있는 모든 꿀단지에 임의의 양만큼 꿀을 담을 수 있다.
이때, 잡은 두개의 구간은 서로 완전히 떨어져 있거나, 서로 완전히 포함해야 한다.
이를 한번의 '작업'이라 정의하자.
모든 1<=i<=N에 대해, i번째 꿀단지에 Ai만큼의 꿀을 채우게 하는 작업의 최소 횟수를 구하시오.
입력
첫 줄에 꿀단지의 개수 N(1<=N<=100,000)이 주어진다.
둘째 줄에 푸가 각 꿀단지에 담고 싶은 꿀의 양이 길이 N의 수열 A1, ..., AN으로 주어진다.
(각 원소는 0 이상 109 이하의 정수이다.)
출력
곰돌이 푸가 최소로 해야 하는 작업의 횟수를 출력하시오.
예제1
입력
3
222
출력
1
예제2
입력
5
23332
출력
2
예제3
입력
6
123213
출력
4
출처
coci 2020/2021 contest5