#P18310. Picturesque Skyline
Picturesque Skyline
Picturesque Skyline
题目描述
你所在的城市有许多高楼,受城市规定限制,每栋楼的高度都互不相同。从远处看,这些楼排成一条直线,并被一些小间隔分成若干组。
一组 栋楼,其中 是正整数,若从左到右的高度满足
$$h_1<h_2<\cdots<h_k<h_{k+1}>h_{k+2}>\cdots>h_{2k}>h_{2k+1},$$就称为一个金字塔形组:左侧恰有 栋楼严格递增,中间是组内最高楼,右侧恰有 栋楼严格递减。同组相邻楼之间没有间隔,相邻组之间留有小间隔。
原题示例图如下:左边的城市由一个含 栋楼的组构成,右边的城市由两个各含 栋楼的组构成。

现在你来到另一个城市。它的楼也排成一条直线,开始时相邻楼之间没有间隔,但未必已经形成这样的若干组。
你有两台机器,必须依次执行以下两个步骤:
- 使用 Group Maker 3000,将原序列切分为一个或多个连续组,每组长度必须为大于 的奇数。这一操作不消耗燃料。
- 使用 Building Swapper 2000,每次交换同一组内的两栋相邻楼,消耗 单位燃料,直到每组都成为金字塔形。
分组完成后,不能交换不同组中的楼。也就是说,必须先确定边界,再在各组内部交换。
求最少需要消耗多少燃料。
输入格式
第一行包含整数 ,表示测试场景数。
每个测试场景:
- 第一行包含整数 ,表示楼的数量;
- 第二行包含 个整数,表示从左到右的楼高。
输出格式
每个测试场景输出一行,表示最少的燃料消耗。
数据范围
- ,且 ;
- ;
- 每个测试场景内,楼高两两不同;
- 所有测试场景的 之和不超过 。
在这些限制下,总能选出合法的分组并完成调整。由每个场景至少包含 栋楼,可推出 。
样例
输入
4
3
1 3 2
6
1 2 4 8 16 32
5
1 2 3 4 5
7
6 4 2 1 3 5 7
输出
0
2
3
9