Trong thế giới của Jujutsu Kaisen, Hắc Thiểm (Black Flash) là hiện tượng cực hiếm xảy ra khi chú lực được truyền vào đòn đánh gần như đồng thời với cú va chạm. Mỗi lần thực hiện thành công Hắc Thiểm sẽ đưa chú thuật sư đến gần hơn với trạng thái \(120\%\) tiềm năng, giúp sức mạnh bộc phát vượt xa giới hạn thông thường.

Tuy nhiên, sau mỗi lần tung Hắc Thiểm, lượng chú lực tiêu hao tăng dần, kỹ thuật này là một kỹ thuật mạnh mẽ chỉ có những chú thuật sư có khả năng quản lý chú lực tốt mới có thể tung ra nhiều Hắc Thiểm liên tiếp. Đòn đánh sẽ giải phóng sức mạnh vật lý và chú lực cùng lúc trong khoảng thời gian cực nhỏ (\(0,000001\) giây).

1. Sát thương bùng nổ: Đòn đánh được khuếch đại sức mạnh lên mức mũ \(2,5\) lần so với thông thường.
2. Hiệu ứng không gian: Xảy ra sự biến dạng không gian cục bộ, đòn đánh biến thành màu đen.
3. Thức tỉnh: Người thi triển rơi vào trạng thái "Zone" (thăng hoa), hiểu rõ bản chất của chú lực và đẩy giới hạn tiềm năng của họ lên mức \(120\%\).

Itadori Yuji có \(n\) đơn vị chú lực được đánh số từ \(1\) đến \(n\). Để tung một Hắc Thiểm, người đó phải tiêu hao liên tiếp một đoạn chú lực \([l, r]\). Sức mạnh của Hắc Thiểm được tính bằng:

Trong đó:

• \(a_i\) là lượng chú lực của đơn vị thứ \(i\).
• \((r - l + 1)\) là số đơn vị chú lực được sử dụng.

Hãy tìm sức mạnh lớn nhất có thể tạo ra.

Input

• Dòng đầu gồm số nguyên \(n\).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\).

Output

• In ra một số nguyên duy nhất là sức mạnh lớn nhất tìm được.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le a_i \le 10^9\)

Example

7
6 2 5 4 5 1 6

17