Cho dãy ~B~ gồm các số nguyên ~B_1, B_2, ..., 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,2,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 xoá đi ít phần tử nhất để dãy còn lại là dãy lõm có độ dài lớn nhất.

Input

• Dòng đầu là số tự nhiên ~N~ ~(2 < N \le 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.

Output

Một số nguyên dương là kết quả của bài toán (ghi số ~0~ nếu không tìm được).

Sample Input 1

10
1 2 3 4 2 5 1 2 3 4

Sample Output 1

6

Sample Input 2

7
7 6 5 4 3 2 1

Sample Output 2

0

Notes

Test 1: Xóa các phần tử: ~1, 2, 3, 5~.