Trung là một người thích ăn cay vô cùng. Hôm nay cậu đang tham gia thử thách ăn cay siêu khủng khiếp.

Cho ~n~ miếng pizza siêu cay được đặt theo vòng tròn, các miếng pizza được đánh số từ ~0~ đến ~n-1~, miếng thứ ~i~ kề với miếng ~(i + 1) \bmod n~. Miếng thứ ~i~ có độ cay là ~a_i~. Để ăn được miếng pizza này, Trung phải có sức chịu đựng là ~k \ge a_i~. Sau khi ăn xong, sức chịu đựng của Trung sẽ được tăng lên bằng ~k + a_i~.

Hãy giúp Trung tìm sức chịu đựng ban đầu nhỏ nhất có thể để có thể hoàn thành thử thách, biết rằng Trung sẽ được phép ăn miếng pizza đầu tuỳ ý, nhưng sau đó Trung chỉ ăn các miếng mà kề với tối đa một miếng khác.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 5 \times 10^5)~ — số lượng miếng pizza.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^{13})~. Các miếng pizza này được xếp theo vòng tròn.

Output

In ra một số nguyên duy nhất là sức chịu đựng ban đầu nhỏ nhất mà Trung cần có để hoàn thành được thử thách.

Scoring

Sample Input 1

4
10 20 15 1

Sample Output 1

9

Notes

Với sức chịu đựng ban đầu là ~9~, Trung có thể chọn ăn lần lượt các miếng pizza ~4~, ~1~, ~3~ và ~2~.