#Z5055. 最长上升子序列

最长上升子序列

给定一个长度为 n 的整数序列,计算其中的最长上升子序列的长度。

输入格式

第一行输入一个整数 n(1n1000)(1 \le n \le 1000),表示序列的长度。

接下来一行 n 个整数 ai(0ai1000000)a_i(0 \le a_i \le 1000000),表示读入的序列元素。

输出格式

输出一个整数,表示序列的最长上升子序列长度。

样例输入

 8
 2 1 5 3 6 4 6 3

样例输出

4