Sau một ngày ăn chơi sinh nhật hết mình, Đôn về nhà và liền leo lên giường. Đột nhiên Đôn nhớ lại mình chưa làm bài tập môn Bitwise 101 dành cho trẻ mầm non. Đề bài ấy như sau:

Đôn vì chơi sinh nhật quá hăng nên giờ chẳng còn tí sức nào để làm bài nữa. Hãy giúp Đôn nhé.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10^6\)) là số lượng phần tử trong dãy.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(0 \leq a_i \leq 10^6\)) là giá trị của các phần tử trong dãy.

Output

• Một số nguyên duy nhất là độ dài dãy con là dãy tốt dài nhất.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(a_i \leq 1\).
• Subtask \(2\) (\(10\%\) số điểm): \(n \leq 10^2\).
• Subtask \(3\) (\(10\%\) số điểm): \(n \leq 10^3\).
• Subtask \(4\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
1 0 1

0

2
5 6

2

6
8 1 3 3 1 2

4