Người nông dân Châu đã xây dựng một chuồng dê có hình dạng là một vòng tròn gồm \(1\) vòng \(n\) phòng. Phòng được đánh số theo chiều kim đồng hồ từ \(1...n\). Xung quanh chu vi của chuồng là \((3≤ n≤ 1000)\).

Mỗi phòng có cửa dẫn đến 2 phòng liền kề và một cửa chính.

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

INPUT FORMAT

Dòng đầu tiên của input chứa \(n\). Mỗi dòng còn lại của \(n\) dòng chứa \(r_1…r_n\)

OUTPUT FORMAT

Hãy ghi ra tổng cự ly tối thiểu mà tổng số các con dê cần di chuyển.

Ví dụ:

Input

5
4
7
8
6
4

Output

48

Trong ví dụ này, giải pháp tốt nhất là để các con bò vào qua cửa của phòng yêu cầu \(7\) con dê.

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House