Một dãy số được gọi là dãy zigzag nếu các phần tử liên tiếp luân phiên tăng-giảm (hoặc giảm-tăng). Nói cách khác, với mọi \(i\): \((a_i - a_{i-1}) * (a_{i+1} - a_i) < 0\).

Cho dãy số \(a_1, a_2, ..., a_N\). Hãy tìm độ dài của dãy con zigzag dài nhất (không nhất thiết liên tiếp).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, ..., a_N\) (\(|a_i| \le 10^9\)).

Kết quả ra

• In ra độ dài dãy zigzag dài nhất.

Ví dụ

Input

7
1 7 4 9 2 5 10

Output

6