题目描述

给定一个长度为N的整数序列，求最长严格上升子序列的长度。

子序列可以不连续，但必须保持原来的先后顺序；严格上升要求后一个数大于前一个数。

输入格式

第一行整数N。第二行N个整数，表示序列。

输出格式

输出最长严格上升子序列的长度。

样例

7
1 7 3 5 9 4 8

4

数据范围

1≤N≤1000；每个整数在0至10000之间。