题目描述

机房门口排着 n 位同学，第 i 位同学的身高为 h_i。他们将按排队顺序依次进入机房，并在机房里按列就坐（每一列视为一组）。

为避免“后排越过前排看屏幕”的情况，同一列内从前到后身高必须单调不增（允许相等）。 当一位同学入场时，他可以：

• 选择某一已有列，并坐在该列最后一位同学的后面；或
• 新开一列，坐在该列的第一个位置。

机房的行数与列数均不受限制。 请计算：在满足规则的前提下，最少需要分成多少列（组）。

等价表述：将序列 $h_1,h_2,\dots,h_n$ 按相对顺序划分为若干个非增子序列，求所需子序列的最小数量。

输入格式

• 第一行一个整数 n，表示总人数。
• 第二行包含 n 个整数 h1 h2 … hn，表示每位同学的身高。

输出格式

输出一个整数，表示最少的列（组）数。

数据范围

• $1 \le n \le 2\times 10^5$
• $0 \le h_i \le 10^9$

样例

输入

7
6 3 6 1 2 4 5

输出

4

说明

一种可行方案：

• 第 1、3、4 位同学组成第 1 列（6, 6, 1）
• 第 2、5 位同学组成第 2 列（3, 2）
• 第 6 位同学单独第 3 列（4）
• 第 7 位同学单独第 4 列（5） 共用 4 列，无法做到更少。