Dãy số nguyên ~B~ gồm ~M~ số ~b_1, b_2, ..., b_M~ được gọi là dãy lồi nếu các phần tử của nó có giá trị giảm dần từ ~b_1~ tới ~b_i~ nào đó, rồi tăng dần tới ~b_M~.

Ví dụ: dãy ~10, 5, 4, 2, 1, 4, 6, 8, 12~ là dãy lồi.

Cho dãy số nguyên ~A~ gồm ~N~ số ~a_1, a_2, ..., a_N~.

Yêu cầu

Hãy xóa bớt một số phần tử của dãy ~A~ và giữ nguyên thứ tự còn lại để được dãy lồi có nhiều phần tử nhất.

Lưu ý: Định nghĩa dãy lồi của đề bài thực chất phải là định nghĩa của dãy lõm. Tuy nhiên, chúng ta sẽ tạm chấp nhận nó trong bài này.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng 1: Ghi số nguyên dương ~N~ ~(N \le 5000)~;
• Dòng 2: Ghi ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(-32000 < a_i < 32000,\ 0 < i \le N)~, các số cách nhau một dấu cách.

Dữ liệu đầu ra

Gồm một số nguyên ~K~ là số lượng phần tử của dãy lồi lớn nhất tìm được (ghi ~0~ nếu không tồn tại dãy lồi).

Ví dụ

Ví dụ 1

INPUT

10
1 2 3 4 2 5 1 2 3 4

OUTPUT

6

Ví dụ 2

INPUT

6
9 8 3 7 2 1

OUTPUT

4

Ví dụ 3

INPUT

5
15 12 8 5 2

OUTPUT

0