Cho dãy số nguyên dương gồm ~N~ số, hãy tìm dãy con tăng dài nhất.

Một dãy con tăng là một dãy số gồm các phần tử ở vị trí ~i_1 < i_2 < ... < i_m~ sao cho ~a_{i_1} < a_{i_2} < a_{i_3} < ... < a_{i_m}~.

Input

• Dòng đầu chứ số ~N (N \leq 10^5)~ là số phần tử của dãy.
• Dòng tiếp theo chứ ~N~ số nguyên dương ~a_i (a_i \leq 10^9)~.

Output

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

Ví dụ

Example Input

5
2 6 3 1 5

Example Output

3

Subtask

• Subtask 1: ~20~% số tests có ~N \leq 10^3, a_i \leq 10^9~.
• Subtask 2: ~40~% số tests có ~N \leq 10^5, a_i \leq 10^5~.
• Subtask 3: ~40~% số tests có ~N \leq 10^5, a_i \leq 10^9~.