페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6136

개구리 뛰기 1s 1024MB

문제

개구리는 암스테르담까지 가고 싶어하는데, 개구리가 암스테르담까지 닿을 수 있는 유일한 방법은 한 정류장에서 다른 정류장으로 이동하는 것이다.

다행히 개구리의 컨디션이 좋아 원하는 만큼 멀리 뛸 수 있다. 하지만 k미터를 뛰려면 개구리는 k^2만큼 에너지를 소비해야 한다.

당연하게도 게으른 개구리는 소비하는 에너지를 최소로 하고 싶어한다.

개구리가 암스테르담까지 오기 위해 필요한 최소 에너지를 계산하는 프로그램을 작성하시오.


입력

첫 줄에 정류장의 총 개수를 나타내는 하나의 정수 N이 주어진다. (2 \le n \le 10^6)

다음 N개의 줄에 i번째 정류장의 위치를 미터로 나타낸 하나의 정수 x_i가 x_i < x_{i+1}을 만족하며 주어진다다. (0 \le x_i \le 10^6)

개구리가 시작하는 지점은 첫 번째 정류장 x_0이며, 암스테르담은 마지막 정류장 x_{n-1}에 위치해 있다.


출력

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


예제 #1

2
0
10
100

예제 #2

3
2
4
6
8

예제 #3

4
10
20
25
26
126

출처

BAPC 2017 Preliminaries Y번
로그인해야 코드를 작성할 수 있어요.