Cho một dãy số ~A_1~ ...An Yêu cầu: tìm số ~K~ lớn nhất sao cho tồn tại dãy chỉ số ~i_1 < i_2 < \dots < i_{2k}~ thỏa mãn ~A_{i_1} < A_{i_{k + 1}}~; ~A_{i_2} < A_{i_{k + 2}} < \dots < A_{i_k} < A_{i_{2k}}~

Input

Dòng đầu ghi số nguyên dương ~N~.

Dòng sau ghi ~N~ số ~A_{i}~ ~(1 \leq i \leq N)~.

Output

Ghi trên một dòng số ~K~ lớn nhất tìm được.

Giới hạn

~N \leq 300~;

~1 \leq A_{i} \leq 10000~.

Sample Input

7
1 2 3 4 5 6 7

Sample Output

3