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~ sao cho: ~B_1>B_2>...>B_i<B_{i+1}<...<B_N~. </p>

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~ (~1 \le A_i \le 10^9~). Hãy lập trình xóa đ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 ≤ 10^5~).

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 duy nhất là độ dài dãy lõm lớn nhất tìm được (ghi số 0 nếu không tìm được).

Sample Test

Input 1

10
1 2 3 4 2 5 1 2 3 4

Output 1

6

Giải thích

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

Input 2

10
7 6 5 4 3 2 1

Output 2

0

Giới hạn

• ~20\%~ số test tương ứng ~20\%~ số điểm với ~2 \le N \le 20~
• ~30\%~ số test tương ứng ~30\%~ số điểm với ~20 < N \le 5000~
• ~50\%~ số test tương ứng ~50\%~ số điểm còn lại không có ràng buộc gì thêm