Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con tăng độ dài \(K\) của \(A\) nếu thoả mãn các điều kiện sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\)

Yêu cầu: Đếm số dãy \(C\) thoả mãn \(K\) lớn nhất có thể, tức là đếm số dãy con tăng dài nhất.

Input

• Dòng thứ nhất gồm số nguyên dương \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).

Output

• In ra số dãy con tăng dài nhất. Vì kết quả có thể rất lớn nên chỉ in kết quả sau khi lấy dư \(20071008\).

Constraints

• \(N\leq 10^5\)
• \(|A_i| \leq 10^9\)

Scoring

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

Example

4
2 3 5 4 

2