Mô tả và yêu cầu

Dãy con lõm

Dãy n số nguyên a1, a2, …, an được gọi là dãy lõm, nếu nó giảm nghiêm ngặt từ a1 đến ak
(1<k<n) nào đó, rồi tăng nghiêm ngặt tới an.
Ví dụ: 10 5 4 2 -1 4 6 8 12 là một dãy lõm có chiều dài 9.
Cho một dãy số nguyên tuỳ ý, bằng cách xóa bớt một số phần tử của dãy và giữ nguyên
trình tự các phần tử còn lại, ta nhận được dãy con lõm.
Yêu cầu Hãy tìm độ dài của dãy con lõm dài nhất.
Dữ liệu vào từ file văn bản DAYLOM.INP gồm n+1 dòng:
- Dòng đầu là n (1≤n≤10000)
- n dòng sau, mỗi dòng một số nguyên ai của dãy (-10000≤ai ≤10000; 1≤i≤n).
Kết quả ghi ra file văn bản DAYLOM.OUT gồm một số nguyên là độ dài của dãy con lõm
dài nhất. Giả sử dữ liệu đã cho luôn có lời giải.
Ví dụ

DAYLOM.INP DAYLOM.OUT Giải thích
11 9 Xoá bớt 2 số được tô màu xám.
10 10
5 5
8 8
4 4
2 2
-1 -1
4 4
6 6
8 8
6 6
12 12