"Ối dồi ôi, ối dồi ôi
Trình là gì mà là trình ai chấm?
Anh chỉ biết làm ba mẹ tự hào,
Xây căn nhà thật to ở một mình hai tấm..."

Trình ai chấm? Trình do bạn chấm. HIEUTHUBA có nhờ bạn chấm "trình" của anh ấy, bằng một tiêu chí được giới ăn-đờ-grao công nhận:

Bạn được cấp ~n~ số điểm của ~n~ show diễn mà HIEUTHUBA đã tham dự (đếm được, đếm được!). Show càng ít điểm thì càng tệ. Ta có công thức tính "trình" của một dãy liên tiếp các show diễn từ show thứ ~i~ tới show thứ ~j~ sẽ là:

"Trình" của một ca sĩ sẽ là phong độ tốt nhất của họ, hay nói cách khác, nó sẽ là giá trị Trình~(i,j)~ lớn nhất có thể, với ~1\le i \le j\le n~.

Yêu cầu: Hãy tính "Trình" của HIEUTHUBA.

Input

• Dòng thứ nhất chứa số nguyên ~n~ ~(1\le n\le 10^6)~ chỉ số show diễn của HIEUTHUBA;

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1\le a_i \le 10^9)~ – là điểm của từng show diễn tương ứng.

Output

• Một dòng chứa một số nguyên dương là "Trình" của HIEUTHUBA.

Scoring

• Subtask 1 (30%): ~n \le 300~.
• Subtask 2 (30%): ~n \le 3000~.
• Subtask 3 (20%): ~n \le 10^5~.
• Subtask 4 (20%): Không có ràng buộc gì thêm.

Sample Input 1

3
1 2 3

Sample Output 1

4

Notes

Để chắc chắn AC, các bạn sẽ cần ios_base::sync_with_stdio(false); cin.tie(nullptr).

Ở test ví dụ, ta lấy dãy show ~[2,3]~. Dãy này có độ dài ~2~, điểm của show tệ nhất là ~2~, nên có "Trình" là ~2\times 2 = 4~. Dãy này có "Trình" tốt nhất.