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 \cdot 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