15001번 - Frog Leaps 다국어

문제

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 i² 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 ≤ 10⁶, the total number of stops.
• Then follow n lines with one integer x_i, the position of the ith stop in meters, with x_i < x_i+1. Here 0 ≤ x_i ≤ 10⁶. The frog’s start location is at the first stop x₀. Amsterdam is located at the last stop x_n−1.

출력

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

제한

힌트