시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 20 16 15 83.333%

문제

It is a little known secret that frogs also like to participate in the BAPC. However, to reach Amsterdam they will need to cross lots of rivers. Fortunately, the frog is in good condition and can jump as far as he wants to go. However, jumping a distance of i meters costs the frog i2 units of energy. The only way the frog can reach Amsterdam is by jumping from stop to stop.

The frog, who is of course lazy, would like to minimize the amount of energy he needs to spend. Can you calculate the minimum amount of energy he needs to spend to reach Amsterdam?

입력

  • On the first line one integer 2 ≤ n ≤ 106, the total number of stops.
  • Then follow n lines with one integer xi, the position of the ith stop in meters, with xi < xi+1. Here 0 ≤ xi ≤ 106. The frog’s start location is at the first stop x0. Amsterdam is located at the last stop xn−1.

출력

  • Print a single integer indicating the minimum number of units of energy the frogs needs to travel to Amsterdam.

예제 입력 1

2
0
10

예제 출력 1

100

예제 입력 2

3
2
4
6

예제 출력 2

8

예제 입력 3

4
10
20
25
26

예제 출력 3

126