有一天,章鱼哥、海绵宝宝和帕特里克决定去海滩。可惜天气不好,小伙伴们没能乘浪。然而,他们决定花时间建造沙堡。
一天结束时,朋友们建造了n座城堡。城堡从1到n编号,第i个城堡的高度等于hi。当朋友们准备离开时,章鱼哥注意到城堡并不是按照高度排序的,这看起来很丑。现在,朋友们将对城堡进行重新排序,以获得条件 hi ≤ hi + 1 对于从 1 到 n - 1 的所有 i 成立。
章鱼哥提出了以下对城堡进行排序的过程:
- 城堡被分成块——连续的城堡组。因此,从 i 到 j 的块将包括城堡 i, i + 1, ..., j。一个街区可能由一座城堡组成。
- 选择分区的方式是让每个城堡都是一个区块的一部分。
- 每个块都独立于其他块进行排序,即序列 hi, hi + 1, ..., hj 已排序。
- 分区应满足以下条件:每个块排序后,序列 hi 也排序。这总是可以通过说整个序列是单个块来实现。
甚至帕特里克也明白,增加分区中的块数量将简化排序过程。现在朋友们要求你计算满足上述所有要求的分区中最大可能的块数。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) - 白天用沙子建造的海绵宝宝、帕特里克和章鱼哥城堡的数量。
下一行包含 n 个整数 hi (1 ≤ hi ≤ 109)。这些整数中的第 i 个对应于第 i 个城堡的高度。
输出
打印有效分区中可能的最大块数。
示例
输入 #1
3 1 2 3
输出 #1
3
输入 #2
4 2 1 3 2
输出 #2
2
注意
在第一个示例中,分区如下所示:[1][2][3]。
在第二个示例中,分区为:[2, 1][3, 2]