The city you live in has a lot of high-rise buildings. Due to some city regulations, each building has a unique height. One day you went to the mountains outside the city. After a long hike you looked at the city to appreciate the beauty of it all. There you noticed something weird, actually two very weird things. The first being, from the right spot all the tall buildings look like they are on a single line. The other is that the buildings are forming multiple unusual groups of pyramid-like patterns with a small gap separating two adjacent groups. Two adjacent buildings in the same group don’t leave any space.

A group of $2k+1$ buildings where $k$ is a positive integer may form a pyramid-like pattern If they meet the following condition. Assuming the heights of buildings are $h_1, h_2, ... , h_{2k+1}$ when sorted by position of the building from left to right. Then the group of buildings need to satisfy $h_1 < h_2 < ... < h_k < h_{k+1} > h_{k+2} > ... > h_{2k} > h_{2k+1}$. So $k$ building in increasing heights followed by the tallest building of the group which is then followed by $k$ buildings in decreasing heights. The city is formed of several such pyramid-like patterns (with small gaps between adjacent groups). This makes the skyline of the city quite picturesque and unique. Assume there are no visible gaps between two adjacent buildings in a group.

Below are examples of two cities. The first one has a single pyramid-like pattern of 5 buildings. The second has 6 buildings in total with two pyramid-like patterns.

Fig: Example cities

When you went to a different city as a tourist you noticed that the buildings in that city are also on a straight line without any gaps between adjacent buildings but they may not be grouped in a pyramid-like pattern. Oh the horror!! Now, hypothetically, let’s assume you have two machines called Building Swapper 2000 and Group Maker 3000. Building Swapper 2000 can swap two adjacent buildings, but requires one unit of fuel to operate. Similarly Group Maker 3000 can split the buildings into one or more groups so that two adjacent groups have a little bit of space between them but it is solar powered, so it doesn’t need any fuel. Now, you have to follow through two steps in order.

• Use the Group Maker 3000 to split the buildings into groups of odd sizes greater than 2. After you have applied this step then there will be one or more groups of buildings (but may not be pyramid-like yet) with a small gap between two adjacent groups.
• Use the Building Swapper 2000 to swap adjacent buildings until each group becomes pyramid-like. You can only swap two adjacent buildings if they are part of the same group.

Finally, you will have some groups of buildings, where all of them are in a pyramid-like pattern and the city will have a picturesque skyline. The question for you is to calculate the minimum cost of fuel required to achieve the goal.

The first line of the input contains an integer T denoting the number of test cases. The first line of each test contains a single integer N (3 ≤ N ≤ 1000, N ≠ 4), the number of buildings in the city. The next line contains N integers denoting the heights of the building (1 ≤ height ≤ 10⁹). It is guaranteed that $\sum$N ≤ 10000 over all test cases and within each test case all the heights are unique.

For each test case print one integer, the minimum amount of fuel required. It can be proven that under the restriction it is always possible to arrange the buildings to achieve the goal.

Contest: NCPC 2023 Onsite Hosted by JU

Problem setter: Nafis Sadique