Dãy con

Cho dãy số nguyên $a_1,a_2,\dots ,a_N$. Dãy số $a_{i_1},a_{i_2},\dots ,a_{i_k}$ được gọi là dãy con của dãy đã cho nếu $1\le i_1<i_2<\dots <i_k\le N$.

Một dãy số $b_1,b_2,\dots ,b_m$ được gọi là dãy hình nón nếu tồn tại vị trí $j$ sao cho:

$b_1<b_2<\dots <b_j>b_{j+1}>\dots >b_m$ (với $1<j<m$).

Yêu cầu: Tìm dãy con hình nón có tổng lớn nhất.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên $N$ $(3\le N\le 1000)$;
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,\dots ,a_N$ $(1\le a_i\le {10}^9)$.

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Dữ liệu ra

Một số nguyên duy nhất là tổng lớn nhất của một dãy con hình nón. Trường hợp không tồn tại dãy con hình nón thì ghi $0$.

Ràng buộc

• $3\le N\le 1000$.
• $1\le a_i\le {10}^9$.
• Có $6/14$ số test ứng với $6/14$ số điểm có $N\le 20$;
• $8/14$ số test còn lại ứng với $8/14$ số điểm không có ràng buộc gì thêm.

Ví dụ