Increasing Subsequence

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Given an array of $n$ integers, find the length of the longest strictly increasing subsequence. A subsequence is obtained by deleting some elements without changing the order of the remaining elements.

Input

The first line contains $n$.

The second line contains $n$ integers.

Output

Print the length of the longest strictly increasing subsequence.

Subtasks

• Subtask 1 — 20%: $n\le2000$.
• Subtask 2 — 30%: $n\le50000$.
• Subtask 3 — 50%: $1\le n\le2\cdot10^5$, $1\le x_i\le10^9$.

Examples

Input

8
7 3 5 3 6 2 9 8

Output

4

Explanation

For example, $3,5,6,9$ is a strictly increasing subsequence of length $4$.