問題
평창 동계올림픽을 잘 치루기 위해 스키장을 만들기 위한 장소를 물색하다가 교통도 편리하고 크기도 적당한 길게 이어진 땅을 확보하였다. 그런데 그 땅은 현재 너무 울퉁불퉁해서 스키장을 만들기 위해서는 우선 높이가 차례대로 단조증가하거나 단조감소하도록 기초작업을 해야 한다. (단조증가란 감소하는 부분이 없이 꾸준히 증가하는 것이고 단조감소란 증가하는 부분이 없이 꾸준히 감소하는 것을 말한다. 즉, 높이가 같은 것은 상관이 없다.) 이러한 작업을 위해 땅을 일정하게 N개의 부분으로 나누고 각 부분의 높이를 구했다.
한 부분의 높이를 조정하는 데에는, 높이거나 낮추기 위해 조정하는 높이만큼의 비용이 든다. 이 땅을 단조증가하거나 단조감소하게 만들기 위해 필요한 최소비용을 구하는 프로그램을 작성하시오.
輸入
첫줄에 땅을 나눈 부분의 수 N (1 ≤ N ≤ 2,000)이 주어진다.
둘째줄부터 나누어진 각 부분의의 높이 Hi (1 ≤ Hi ≤ 1,000,000,000)가 주어진다.
輸出
첫줄에 길을 고르게 하는 데 드는 비용을 출력한다. 결과값은 231-1 이하의 값이다.
範例
7
1
3
2
4
5
3
9
3
需要登入才能撰寫程式碼。