Longest Increasing Subsequence (LIS) - Classic Problems | Repovive

CLS36. Longest Increasing Subsequence (LIS)

2s256 MB

Given an array of $n$ integers, find the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived by deleting some or no elements without changing the order of remaining elements. The subsequence must be strictly increasing (each element is greater than the previous one).

Constraints

$1 \le n \le 5000$
$1 \le a_i \le 10^9$

Input

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

Output

$\text{length of LIS}$

Samples

Input

8
10 9 2 5 3 7 101 18

Explanation

For this input, the required output is 4.

Output

Input

5
1 2 3 4 5

Explanation

For this input, the required output is 5.

Output

Input

5
5 4 3 2 1

Explanation

For this input, the required output is 1.

Output

CLS36. Longest Increasing Subsequence (LIS)

2s256 MB

Given an array of $n$ integers, find the length of the longest strictly increasing subsequence.

Constraints

$1 \le n \le 5000$
$1 \le a_i \le 10^9$

Input

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

Output

$\text{length of LIS}$

Samples

Input

8
10 9 2 5 3 7 101 18

Explanation

For this input, the required output is 4.

Output

Input

5
1 2 3 4 5

Explanation

For this input, the required output is 5.

Output

Input

5
5 4 3 2 1

Explanation

For this input, the required output is 1.

Output