Cho một dãy số \(A\) gồm \(n\) phần tử \(a_1, a_2, \ldots, a_n\). Một dãy con \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\) của \(A\) được gọi là dãy con hình kim tự tháp nếu như trong dãy đó tồn tại một vị trí \(i_{mid}\) thỏa mãn:

Hãy tìm dãy con hình kim tự tháp dài nhất trong dãy đã cho?

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) - số phần tử của dãy số \((1 \le n \le 2 * 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9)\) phân tách nhau bởi dấu cách.

Output

• Số nguyên duy nhất là độ dài dãy con hình kim tự tháp dài nhất tìm được.

Scoring

• Subtask 1 \((30\%)\): \(1 \le n \le 20\).
• Subtask 2 \((40\%)\): \(1 \le n \le 5000\).
• Subtask 3 \((30\%)\): \(1 \le n \le 2 * 10^5\).

Sample

6
4 2 3 5 3 6

4

5
3 2 1 2 3

3