Page not loading? Try clicking here.
Placeholder

#6136

개구리 뛰기 1s 1024MB

Problems

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

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

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

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


Input

첫 줄에 정류장의 총 개수를 나타내는 하나의 정수 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}에 위치해 있다.


Output

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


Example #1

2
0
10
100

Example #2

3
2
4
6
8

Example #3

4
10
20
25
26
126

Source

BAPC 2017 Preliminaries Y번
You must sign in to write code.