题目描述

你会得到按一定顺序排列的 $n$ 个立方体，而你的任务就是用它们建造高塔。每当两个立方体叠在一起时，上面的立方体必须小于下面的立方体。

你必须按照给定的顺序处理方块。你既可以将立方体放在已有塔的顶部，也可以新建一座塔。塔的最小数量是多少？

输入格式

第一行输入的是整数 $n$，代表立方体的个数。

第二行包含 $n$ 个整数 $k_1, k_2, \ldots, k_n$，分别代表立方体的大小。

输出格式

输出一个整数，表示塔的最小数量。

样例

5
3 8 2 1 5

2

数据范围

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