#P18310. Picturesque Skyline

Picturesque Skyline

Picturesque Skyline

题目描述

你所在的城市有许多高楼,受城市规定限制,每栋楼的高度都互不相同。从远处看,这些楼排成一条直线,并被一些小间隔分成若干组。

一组 2k+12k+1 栋楼,其中 kk 是正整数,若从左到右的高度满足

$$h_1<h_2<\cdots<h_k<h_{k+1}>h_{k+2}>\cdots>h_{2k}>h_{2k+1},$$

就称为一个金字塔形组:左侧恰有 kk 栋楼严格递增,中间是组内最高楼,右侧恰有 kk 栋楼严格递减。同组相邻楼之间没有间隔,相邻组之间留有小间隔。

原题示例图如下:左边的城市由一个含 55 栋楼的组构成,右边的城市由两个各含 33 栋楼的组构成。

原题的单组与多组金字塔示例

现在你来到另一个城市。它的楼也排成一条直线,开始时相邻楼之间没有间隔,但未必已经形成这样的若干组。

你有两台机器,必须依次执行以下两个步骤:

  1. 使用 Group Maker 3000,将原序列切分为一个或多个连续组,每组长度必须为大于 22 的奇数。这一操作不消耗燃料。
  2. 使用 Building Swapper 2000,每次交换同一组内的两栋相邻楼,消耗 11 单位燃料,直到每组都成为金字塔形。

分组完成后,不能交换不同组中的楼。也就是说,必须先确定边界,再在各组内部交换。

求最少需要消耗多少燃料。

输入格式

第一行包含整数 TT,表示测试场景数。

每个测试场景:

  • 第一行包含整数 NN,表示楼的数量;
  • 第二行包含 NN 个整数,表示从左到右的楼高。

输出格式

每个测试场景输出一行,表示最少的燃料消耗。

数据范围

  • 3≤N≤10003\le N\le1000,且 N≠4N\ne4;
  • 1≤hi≤1091\le h_i\le10^9;
  • 每个测试场景内,楼高两两不同;
  • 所有测试场景的 NN 之和不超过 1000010000。

在这些限制下,总能选出合法的分组并完成调整。由每个场景至少包含 33 栋楼,可推出 T≤3333T\le3333。

样例

输入

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