#P18233. Dolls
Dolls
Dolls
David 得到了 个大小互不相同的俄罗斯套娃,并将它们从左到右排成一行。最初第 个位置只有一个大小为 的套娃。
一个位置中可能已经包含多个套娃。设当前第 个位置中最小套娃的大小为 ,最大套娃的大小为 。当且仅当
时,可以将相邻两个位置 和 中的套娃合并:新位置包含这两个原位置中的全部套娃,放在位置 ;原来在 之后的所有位置向左移动一位。
例如,初始排列为 时,可以依次进行:
- 合并前两个位置,得到 。
- 合并后两个位置,得到 。
- 合并剩余两个位置,将全部套娃放在一起。
采用最优策略,最多可以进行多少次合并?
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例包含两行:
- 第一行一个整数 。
- 第二行 个整数 ,表示最初的套娃大小。
数据范围:
- ;
- ;
- ,且任意两个 不同,即 为 的排列;
- 同一输入文件所有测试用例的 之和不超过 。
输出格式
每个测试用例输出一行一个整数,表示最多可以进行的合并次数。
样例
8
4
2 1 4 3
4
1 4 2 3
4
3 1 4 2
5
1 3 5 2 4
5
1 4 2 5 3
5
2 5 3 1 4
6
1 3 6 5 2 4
6
2 5 1 3 6 4
3
3
2
3
3
3
4
4