26646번 - 알프스 케이블카

문제

ALPS 부원들은 친목 도모를 위해 다 같이 알프스 산맥으로 여행을 떠났다! 알프스 산맥은 $N$개의 산이 겹치거나 빈 부분 없이 일렬로 나열된 형태이며, 왼쪽에서부터 $i$번째에 위치한 산은 빗변을 아래로 하며 높이가 $H_i$인 직각 이등변 삼각형이다.

ALPS 부원들은 체력이 좋지 않기 때문에 1ドル$번 산에서 시작해 $N$번 산에서 끝나는 케이블카 노선을 설치해 산을 오르려 한다. 노선을 설치하는 법은 다음과 같다.

1. 1ドル$번 산의 정상과 다른 산의 정상을 직선으로 잇는 와이어를 설치하고, 다시 그 산의 정상에서 다른 산의 정상으로 와이어를 설치한다. 이 때 와이어는 산을 가로질러 설치될 수 있다.
2. 이를 $N$번 산을 끝으로 할 때까지 자유롭게 반복한다.

각 와이어의 설치 비용은 설치해야 할 와이어 길이의 제곱과 같으며 노선의 설치 비용은 사용한 와이어의 설치 비용의 합이다. ALPS 부원들을 위해 1ドル$번 산에서 시작해 $N$번 산에서 끝나는 노선을 설치하기 위한 최소 비용을 구해보자.

입력

첫 번째 줄에 알프스 산맥을 이루는 산의 수 $N$이 주어진다. $(2 \leq N \leq 50,000円)$

두 번째 줄에 각 산의 높이 $H_1, H_2, \cdots, H_N$이 공백으로 구분되어 정수로 주어진다. $(1 \leq H_i \leq 100)$

출력

1ドル$번 산에서 시작해 $N$번 산에서 끝나는 노선을 설치하기 위한 최소 비용을 출력한다.

제한

힌트