여러분은 "곰돌이 푸"가 여자였다는 사실을 아셨나요? 저는 방금 처음 알았습니다.

곰돌이 푸는 꿀을 꿀단지에 모으는 취미를 갖고 있다.

푸의 남자친구 생일이 곧 다가오기에, 선물로 N개의 꿀단지를 준비하려 한다.

속이 빈 꿀단지를 선물하기는 좀 그래서, i번째 꿀단지에는 Ai만큼의 꿀을 채워넣으려 한다.

푸는 엄연히 곰이기 때문에, 꿀을 일일이 채우는 것이 귀찮다.

대신 어떤 구간 l~r을 잡아, 해당 구간 안에 있는 모든 꿀단지에 임의의 양만큼 꿀을 담을 수 있다.

이때, 잡은 두개의 구간은 서로 완전히 떨어져 있거나, 서로 완전히 포함해야 한다.

이를 한번의 '작업'이라 정의하자.

모든 1<=i<=N에 대해, i번째 꿀단지에 A_i만큼의 꿀을 채우게 하는 작업의 최소 횟수를 구하시오.

곰돌이 푸 timer 1s memory 1024MB

곰돌이 푸 1s 1024MB