题目描述

有一天，码头上陆续运来了 $n$ 只集装箱，到了第二天，这些集装箱会全部装船出海，第 $i$ 号集装箱属于第 $a_i$ 号轮船的货物。

箱子到港的时候，为了节约场地，可以将一些箱子竖直叠放。但要满足两个要求：

• 首先，不能让先到的箱子堆到后来的箱子的上方，箱子到港的顺序就是箱子的编号，$1$ 号集装箱最先到港；
• 其次，在装船的时候，每个箱子的上方应该没有装到其他船的箱子。船舶到港的顺序就是船舶的编号，$1$ 号船最先到港。

请帮助小爱计算一下，为了满足装货的要求，至少需要将这些箱子堆成多少堆。

输入格式

• 第一行：单个整数表示 $n$。
• 第二行：$n$ 个整数表示 $a_1,a_2,\cdots,a_n$。

输出格式

• 单个整数：表箱子最少可以分成多少堆。

5
5 4 3 2 1

1

样例解释 1

五只箱子可以堆在一起。

6
5 4 4 3 1 2

2

样例解释 2

5 4 4 3 1一堆，2单独一堆，也存在其他最优方案

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 500$；
• 对于 $60\%$ 的数据，$1\leq n\leq 5000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 100,000$；
• $1\leq a_i\leq n$。