Dãy sóng Wavio

Một dãy số được gọi là dãy Wavio nếu nó có dạng: tăng ngặt dần lên một phần tử đỉnh, sau đó giảm ngặt dần xuống. Cả phần tăng (bên trái đỉnh) và phần giảm (bên phải đỉnh) đều phải có ít nhất một phần tử. Ví dụ \(1, 2, 3, 4, 5, 2, 1\) là dãy Wavio độ dài \(7\).

Cho dãy \(A\) gồm \(N\) số nguyên, hãy tìm độ dài lớn nhất của một dãy con (không nhất thiết liên tiếp) của \(A\) là dãy Wavio. Nếu không tồn tại dãy con Wavio nào, in ra \(1\).

Input

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

In ra một số nguyên: độ dài lớn nhất của dãy con Wavio (hoặc \(1\) nếu không có).

Constraints

• \(2 \le N \le 5000\)
• \(|A_i| \le 10^9\)

Sample Input 1

9
2 4 6 9 7 5 3 3 1

Sample Output 1

8

Sample Input 2

4
8 6 6 3

Sample Output 2

1

Explanation

Ví dụ 1: chọn \(2, 4, 6, 9, 7, 5, 3, 1\) (bỏ một số \(3\)) được độ dài \(8\). Ví dụ 2: dãy không có phần tăng nào nên không có dãy con Wavio, kết quả là \(1\).