题目描述

一个数的序列 $b_i$，当 $b_1​<b_2​<...<b_s$ ​的时候，我们称这个序列是上升的。对于给定的一个序列 $(a_1​,a_2​,...,a_N​)$，我们可以得到一些上升的子串，这里 $1≤i_1​<i_2​<...<i_K​≤N$。比如，对于序列 (1,7,3,5,9,4,8)，有它的一些上升子串，如 (1,7)，(3,5,9) 等等。这些子串中最长的长度是 3，比如子串 (3,5,9)。

你的任务，就是对于给定的序列，求出最长上升子串的长度。

输入格式

输入的第一行是序列的长度 N。（1≤N≤1000）

第二行给出序列中的 N 个整数，这些整数的取值范围都在0到 10000。

输出格式

最长上升子串长度。

样例

8 
1 2 1 3 4 6 2 7

4