Là một người yêu thích kiến trúc đương đại, Farmer John đã xây một chuồng mới có dạng một đường tròn hoàn hảo. Bên trong, chuồng gồm một vòng tròn có \(n\) phòng, được đánh số theo chiều kim đồng hồ từ \(1 \ldots n\) quanh chu vi chuồng (\(3 \leq n \leq 1\,000\)). Mỗi phòng đều có cửa thông sang hai phòng bên cạnh và một cửa mở ra bên ngoài chuồng.

Farmer John muốn đúng \(r_i\) con bò ở lại trong mỗi phòng \(i\) (\(1 \leq r_i \leq 100\)). Để lùa bò vào chuồng một cách trật tự, ông dự định mở khóa cửa ngoài của đúng một phòng, cho phép đàn bò đi vào qua cửa đó. Sau đó, mỗi con bò đi theo chiều kim đồng hồ qua các phòng cho đến khi đến một vị trí thích hợp. Farmer John muốn mở khóa cửa ngoài sao cho tổng quãng đường mà đàn bò phải đi là nhỏ nhất. Hãy xác định tổng quãng đường nhỏ nhất mà đàn bò phải đi nếu ông chọn cửa tốt nhất để mở khóa. Quãng đường một con bò đi được tính bằng số cửa bên trong mà nó đi qua.

Dữ liệu vào

Dòng đầu tiên chứa \(n\). Mỗi dòng trong \(n\) dòng còn lại lần lượt chứa \(r_1 \ldots r_n\).

Dữ liệu ra

In tổng quãng đường nhỏ nhất mà đàn bò phải đi.

Ví dụ

5
4
7
8
6
4

48

Nguồn

USACO 2016 February Contest, Bronze - Circular Barn: https://usaco.org/index.php?page=viewproblem2&cpid=616

Tác giả: Brian Dean.