#P18052. Dolls 2
Dolls 2
Dolls 2
有 个大小互不相同的套娃,从左到右排列,初始每个格子中只有一个套娃,第 个的大小为 。
对于当前第 个格子,记其中最小、最大的套娃大小分别为 。只有当
时,才允许合并相邻的两个格子 。合并后,一个格子包含原来两个格子中的所有套娃,其右侧格子依次左移。
你必须不断进行合法合并,直到再也无法合并任何两个相邻格子。求整个过程中最少需要进行多少次合并。
输入格式
第一行整数 ,。每个用例包含两行:
- 一个整数 ,。
- 个整数 ,它们是 的一个排列。
所有用例的 之和不超过 。
输出格式
每个用例输出一行一个整数,表示最少合并次数。
样例
输入:
5
5
1 2 3 5 4
5
1 2 3 4 5
5
1 3 5 4 2
5
1 5 2 4 3
5
1 2 4 3 5
输出:
3
4
3
2
3