Cho mảng A có N phần tử nguyên. Tập con của mảng A là tập gồm các phần tử ~A_{i1}, A_{i2},...,A_{ik}~ thỏa điều kiện ~1 \le i1 < i2 < ... < ik \le n~. Một cách khác để mô tả dãy con là dãy gồm các phần tử còn lại của dãy A sau khi xóa đi một số phần tử (cũng có thể không cần xóa phần tử nào) và giữ nguyên tính thứ tự của các phần tử còn lại.
Tập con này được gọi là tập ZIGZAG nếu thỏa một trong 2 điều kiện sau: $$A_{i1} \lt A_{i2} \gt A_{i3} \lt A_{i4} ...\ hoặc \ A_{i1} \gt A_{i2} \lt A_{i3} \gt A_{i4} ... $$

Yêu cầu:

Xác định độ dài tập con ZIGZAG dài nhất trên A.

Dữ liệu:

Dòng đầu ghi số nguyên N là số phần tử của mảng A.~(1≤N≤10^5)~
Dòng thứ hai ghi N số nguyên dương là các phần tử của mảng A. Giá trị các phần tử không vượt quá ~10^6~

Kết quả:

Dòng duy nhất ghi độ dài dãy con ZIGZAG dài nhất xác định được.
Dãy con chỉ có 1 phần tử được xem là dãy ZIGZAG độ dài 1.

Input 1:

6
1 7 4 9 2 5

Output 1:

6

Giải thích:

Toàn bộ dãy là dãy ZIGZAG

Input 2:

10
1 17 5 10 13 15 10 5 16 8

Output 2:

7

Có một số dãy con đạt được độ dài này. Một phương án là 1,17,10,13,10,16,8
TOPCODER-ZIGZAG