Cho dãy B gồm các số nguyên ~ b_1, b_2,b_3,…,b_n ~ được gọi là dãy lõm nếu tồn tại chỉ số ~ i~ ~(1<i<n) ~ sao cho ~ b_1<b_2<…<b_i<b_{i+1}<…b_n ~. Ví dụ dãy ~ B=10, 5,4,2,1,4,6,8,12 ~ được gọi là dãy lõm, còn dãy ~ B={10,5,7,1,4,6,8,12} ~ không được gọi là dãy lõm.

Yêu cầu: Cho trước dãy ~A~ gồm ~ n ~ số nguyên dương ~ a_1,a_2,…,a_n ~. Hãy lập trình xóa ít nhất hần tử để được dãy còn lại là dãy lõm có độ dài lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên là số tự nhiên ~ n (2<n≤5000) ~

• Dòng tiếp theo là ~ n ~ số nguyên dương của dãy số, mỗi số cách nhau tối thiểu một khoảng trắng.

Kết quả:

• Một số nguyên là kết quả bài toán, ghi số 0 nếu không tìm được

Ví dụ: Input 1:

10
1 2 3 4 2 5 1 2 3 4 

Output 1:

6 

Input 2:

7
7 6 5 4 3 2 1 

Output 2:

0