현대 건축을 좋아하는 Farmer John은 완전한 원형 헛간을 지었습니다. 안에는 둘레를 따라 고리 모양으로 방 $n$개가 있으며, 시계 방향으로 $1 \ldots n$의 번호가 있습니다($3 \leq n \leq 100,000$). 각 방에 두 이웃 방으로 가는 문과 바깥으로 나가는 문이 있습니다.

소 $n$마리를 각 방에 정확히 한 마리씩 두고 싶습니다. 하지만 혼란스러운 소들은 아무 문에나 줄을 서며 같은 문에 여러 마리가 서기도 합니다. 방 $i$의 바깥문 앞에 정확히 $c_i$마리가 있으므로 $\sum c_i = n$입니다.

각 소는 처음 줄을 선 문으로 들어가서 적당한 목적지까지 시계 방향으로 방들을 지납니다. 문 $d$개를 지나면 에너지 $d^2$을 씁니다. 각 방에 한 마리씩 배치하는 데 필요한 총 에너지의 최솟값을 구하세요.

입력

첫 줄에는 $n$이 주어집니다. 다음 $n$개 줄에는 $c_1 \ldots c_n$이 순서대로 한 줄에 하나씩 주어집니다.

출력

소들이 사용하는 최소 총 에너지를 출력하세요.

예제

입력 1

10
1
0
0
2
0
0
1
2
2
2

출력 1

33

문제 작성: Brian Dean