Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là xác định dãy con tăng dài nhất của mảng, tức là, tìm dãy con dài nhất trong đó tất cả các phần tử đều lớn hơn phần tử trước đó.

Một dãy con là một dãy có thể thu được từ mảng bằng cách xóa một số phần tử mà vẫn không thay đổi thứ tự của các phần tử còn lại.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 2 \times 10^{5})\) - kích thước của mảng.
• Sau đó có \(n\) số nguyên \(x_{1}, x_{2}, \dots, x_{n}\) \((1 \leq x_{i} \leq 10^{9})\) - các phần tử của mảng.

Output

• In độ dài của dãy con tăng dài nhất.

Example

8
7 3 5 3 6 2 9 8

4