装卸问题(Loading Problem)

题目描述

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

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

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

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

输入格式

• 第一行：单个整数表示 n。
• 第二行：n 个整数表示 a₁,a₂,⋯,aₙ。

输出格式

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

数据范围

• 对于 30% 的数据，1 ≤ n ≤ 500；
• 对于 60% 的数据，1 ≤ n ≤ 5000；
• 对于 100% 的数据，1 ≤ n ≤ 100,000；
• 1 ≤ aᵢ ≤ n。

样例输入 #1

5 5 4 3 2 1

样例输出 #1

1

说明：五只箱子可以堆在一起。

样例输入 #2

6 5 4 4 3 1 2

样例输出 #2

2

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

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐。

测试点分布