Quả quýt

Có \(N\) đĩa được xếp thành hàng. Đĩa thứ \(i\) từ bên trái chứa \(A_i\) quả quýt.

Bạn được phép chọn một bộ ba số nguyên \((l, r, x)\) thoả mãn:

• \(1 \le l \le r \le N\),
• \(1 \le x\),
• Với mọi \(i\) sao cho \(l \le i \le r\), ta có \(x \le A_i\).

Sau đó bạn sẽ lấy \(x\) quả quýt từ mỗi đĩa từ \(l\) đến \(r\). Hỏi bạn có thể lấy được nhiều nhất bao nhiêu quả quýt nếu chọn \((l, r, x)\) một cách tối ưu?

\InputFile

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) (\(1 \le A_i \le 10^5\)).

\OutputFile

In ra một số nguyên --- số quả quýt tối đa có thể lấy được.

\Examples

\beginexample
\exmp6
2 4 4 9 4 9
20

\endexample

\beginexample
\exmp6
200 4 4 9 4 9
200

\endexample

\Scoring

• Subtask 1 (23 điểm): \(N \le 1000\)
• Subtask 2 (12 điểm): Dãy \(A\) giảm dần, tức là \(A_1 \ge A_2 \ge \ldots \ge A_N\)
• Subtask 3 (65 điểm): Không có ràng buộc gì thêm