문제

현성이는 현대적인 건축 양식에 관심이 많아, 원형으로 된 새로운 동아리방을 만들었다. 동아리방 내부는 $n$개의 방이 원형으로 배치된 구조이며, 시계 방향으로 $1$번부터 $n$번까지 번호가 매겨져 있다. ($3 \le n \le 1\,000$) 각 방은 시계 방향과 반시계 방향으로 인접한 두 방으로 연결되는 내부 문이 있고, 외부와 바로 연결되는 문도 하나씩 있다.

현성이는 각 방 $i$에 정확히 $r_i$명의 부원을 배치하려고 한다. ($1 \le r_i \le 100$) 부원들을 질서 있게 입장시키기 위해, 현성이는 단 하나의 방에 있는 외부 문만 열어 모든 부원이 그 문을 통해 들어오게 할 계획이다. 입장한 부원들은 시계 방향으로 이동하며 자신의 목적지인 방에 도착할 때까지 이동한다.

현성이는 부원들의 총 이동 거리 합이 최소가 되도록 어떤 외부 문을 열지 결정하려고 한다. 최적의 문을 선택했을 때, 모든 부원이 이동해야 하는 총 거리 합의 최솟값을 구하시오. 부원 한 명이 이동하는 거리는 그 부원이 통과하는 내부 문의 개수이다.

입력

첫째 줄에 방의 개수 $n$이 주어진다. ($3 \le n \le 1\,000$)

둘째 줄부터 $n$개의 줄에 걸쳐 각 방에 필요한 부원 수 $r_1, r_2, \dots, r_n$이 한 줄에 하나씩 주어진다. ($1 \le r_i \le 100$)

출력

모든 부원이 이동한 총 거리 합의 최솟값을 출력한다.

예제 입력 1

5
4
7
8
6
4

예제 출력 1

48