Description

给定一个整数序列A1A2A3….An。求它的一个递增子序列，使子序列的元素个数尽量多，元素不一定要求连续。

Format

Input

第1行：1个整数n(1<=n<=500000)，表示序列中元素的个数.

第2行-n+1行：每行1个整数x(-1000000<=x<=1000000)，第i+1行表示序列中的第i个元素。

Output

第1行：1个整数k，表示最长上升子序列的长度。

Samples

8
1
3
2
4
3
5
4
6

5

Limitation

1s, 1024KiB for each test case.