개구리 점프

시간 제한2초메모리 제한512 MB

요약

정렬된 위치가 주어질 때 첫 번째 정류장에서 마지막 정류장까지 이동하는 데 필요한 제곱 거리 합의 최솟값을 구한다.

난이도: 보통10점 중 4점
유형: 그리디, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

개구리도 암스테르담에서 열리는 프로그래밍 대회에 나가고 싶어 한다. 대회장에 가려면 강을 여러 개 건너야 한다. 다행히 이 개구리는 몸 상태가 좋아서 원하는 거리만큼 한 번에 뛴다. 다만 $i$ 미터를 뛰면 에너지를 $i^2$ 만큼 쓴다. 강을 건너는 방법은 발판에서 발판으로 뛰는 것뿐이다.

게으른 개구리는 쓰는 에너지를 최대한 줄이고 싶다. 암스테르담에 도착하는 데 필요한 에너지의 최솟값을 구하라.

입력

첫째 줄에 발판의 개수 $n$ 이 주어진다 ( $2 \le n \le 10^6$ ).

다음 $n$ 개 줄에는 $i$ 번째 발판의 위치 $x_i$ 가 미터 단위로 한 줄에 하나씩 주어진다 ( $0 \le x_i \le 10^6$ , $x_i < x_{i+1}$ ).

개구리는 첫 번째 발판 $x_0$ 에서 출발하고, 암스테르담은 마지막 발판 $x_{n-1}$ 에 있다.

출력

개구리가 암스테르담까지 가는 데 쓰는 에너지의 최솟값을 정수 하나로 출력한다.

예제3

예제 1
입력
```
2
0
10
```
예상 출력
```
100
```
예제 2
입력
```
3
2
4
6
```
예상 출력
```
8
```
예제 3
입력
```
4
10
20
25
26
```
예상 출력
```
126
```