你将会按照某种顺序得到 n 个立方体，你的任务是用它们建造塔。当两个立方体一个在另一个上面时，上面的立方体必须比下面的立方体小。

你必须按照给定的顺序处理立方体。你可以始终将立方体放在现有塔的顶部，或者开始一个新的塔。最少需要多少个塔？

输入

第一行输入一个整数 n：立方体的数量。 接下来一行包含 n 个整数$k_1,k_2,\ldots,k_n$：立方体的大小。

输出

输出一个整数：最少的塔数量。

约束

$1 \le n \le 2 \cdot 10^5$

$1 \le k_i \le 10^9$

示例

输入：

5
3 8 2 1 5

输出：

2