描述

给出N与N个数
求N个数的最长上升子序列

输入

第一行一个整数N
第二行N个整数

输出

一行一个整数，为最长上升子序列长度

样例

输入

2
1 2

输出

2

范围

20% 1<=N<=10
50% 1<=N<=100
80% 1<=N<=1000
100% 1<=N<=\(10^6\) 1<=所有数<=\(10^7\)

限制

1000ms
128M