ez_code   4년 전

문제

개구리도 BAPC에 참가하고 싶어 한다는 것은 잘 알려지지 않은 사실입니다. 하지만 암스테르담까지 오려면 개구리는 많은 강을 건너야 합니다. 다행히 개구리의 컨디션이 좋아 원하는 만큼 멀리 뛸 수 있죠. 하지만 i미터를 뛰려면 개구리는 i2만큼 에너지를 소비해야 합니다. 개구리가 암스테르담까지 닿을 수 있는 유일한 방법은 한 정류장에서 다른 정류장으로 이동하는 것입니다.

당연하게도 게으른 개구리는 소비하는 에너지를 최소로 하고 싶어 합니다. 개구리가 암스테르담까지 오기 위해 필요한 최소 에너지를 계산할 수 있습니까?

입력

- 첫 줄에 정류장의 총 개수를 나타내는 하나의 정수 2 <= n <= 106이 주어집니다.

- 다음 n개의 줄에 i번째 정류장의 위치를 미터로 나타낸 하나의 정수 xi가 xi < xi+1을 만족하며 주어집니다. 또한 0 <= xi <= 106입니다. 개구리가 시작하는 지점은 첫 번째 정류장 x0입니다. 암스테르담은 마지막 정류장 xn-1에 위치해 있습니다.

출력

개구리가 암스테르담까지 가기 위해 필요한 최소 에너지를 나타내는 하나의 정수를 출력합니다.

댓글을 작성하려면 로그인해야 합니다.