Longest Increasing Subsequence II

Problem Description

Given an array $a_1, a_2, \dots, a_n$ of length $n$, find the length of its longest increasing subsequence. That is, we want the largest $m$ and array $p_1, p_2, \dots, p_m$ such that $1 \leq p_1 < p_2 < \dots < p_m \leq n$ and $a_{p_1} < a_{p_2} < \dots < a_{p_m}$.

Input Format

The first line contains an integer $n$.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

One number: the answer.

Sample Input

6
3 7 4 2 6 8

Sample Output

4

Constraints

All data guarantee $1 \leq n \leq 100000, 1 \leq a_i \leq 10^9$.