문제

준모는 현대적인 건축 양식에 매료되어 원형으로 된 새로운 동아리방을 지었다. 동아리방 내부는 시계 방향으로 $1$부터 $n$까지 번호가 매겨진 $n$개의 방이 고리 모양으로 배치되어 있다. ($3 \le n \le 100\,000$) 각 방은 이웃한 두 개의 방과 연결되는 문이 있으며, 외부와 통하는 문도 하나씩 있다.

준모는 $n$명의 동아리 부원을 각 방에 정확히 한 명씩 배치하려고 한다. 하지만 부원들이 무작위로 문 앞에 모이는 바람에, 어떤 문 앞에는 여러 명의 부원이 서 있고 어떤 문 앞에는 아무도 없는 상황이 발생했다. $i$번 방의 문 앞에 줄을 선 부원의 수는 $c_i$명이며, 부원 수의 총합은 $n$이다. ($\sum c_i = n$)

준모는 다음과 같은 방식으로 부원들을 배치하기로 했다. 각 부원은 자신이 처음에 줄을 섰던 문을 통해 동아리방으로 들어온다. 그 후, 시계 방향으로 이동하며 적절한 방을 찾아 들어간다. 부원이 $d$개의 문을 통과할 때 소모되는 에너지는 $d^2$이다. 모든 부원이 각 방에 한 명씩 들어가도록 배치할 때, 소모되는 에너지 총합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $n$이 주어진다. ($3 \le n \le 100\,000$)

이어서 $n$개의 줄에 $c_1$부터 $c_n$까지의 값이 한 줄에 하나씩 주어진다.

출력

부원들이 소모하는 에너지 총합의 최솟값을 출력한다.

예제 입력 1

10
1
0
0
2
0
0
1
2
2
2

예제 출력 1

33