题目描述

给定一个长度为$n$的数组，要求计算出数组中最长上升子数组的长度，例如，数组$[1,3,2,4,6]$，$[1,3]$是子数组，$[1,3,4]$不是子数组，是子序列（子数组必须要是连续的一段区间）

输入描述

第一行输入一个整数$n(1\le n\le 10^5)$，表示数组的长度

第二行输入$n$个整数 $w_1,w_2,...w_n(-10^9\le w_i \le 10^9)$，表示数组的$n$个数字

输出描述

输出一个整数，表示数组中最长上升子数组的长度

样例

输入

5
1 3 2 4 6

输出

3