J. Just Too Much Procrastination
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are currently taking the course AlgoHell and have procrastinated a bit too much. Today is already the deadline for the current problem. Luckily, you have an algorithm which is correct, but it has a terrible runtime complexity. Therefore, you break into ETH's top secret super computer in the dome at the top of HG. Unfortunately, the complexity of your algorithm is so bad that even on the super computer, it runs too slowly. It will not be able to give you the result in time for your deadline.

To speed up the computation, you need to cool down the super computer. It has $$$n$$$ different server racks, where $$$n$$$ is even since the server architects can only buy racks in bundles of 2. Each rack has a unique heat level $$$a_i$$$ since your parallelization does not split up the workload evenly. The racks are all aligned in a row; rack $$$i$$$ is next to rack $$$i+1$$$. You want adjacent racks with a low heat level to cool their warmer neighbors. This works best if the difference between the heat levels is big. Therefore, you want to maximize the sum of absolute differences of heat levels in adjacent server racks:

$$$$$$\max\sum_{i=2}^n |a_{i-1} - a_i|$$$$$$

Since you have been here before, you know that all adjacent racks are connected with a wire. You can use this wire to transfer the workloads and swap the heat levels of one server rack with an adjacent one. However, you also want to minimize the number of swaps, since each swap takes about 1 minute and you have to submit the answer before the deadline.

Now you want to answer 2 questions to determine whether the computation will finish in time:

  1. How much cooling can you achieve — what is the maximum sum of absolute differences in heat levels?
  2. How much time does it take to reach this cooling efficiency — what is the minimum number of adjacent swaps to reach this sum?
Input

The first line of input contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$) — the number of test cases. Then $$$t$$$ lines follow, each describing one test case.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 4 \cdot 10^5$$$) — the number of server racks in the super computer. Since the server architects are not weird, $$$n$$$ is guaranteed to be even.

The second line of each test case contains n distinct integers $$$a_1,...,a_n$$$ ($$$1 \leq a_i \leq n$$$), where $$$a_i$$$ is the heat level of the $$$i$$$–th rack.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

For each test case, output two integers: the maximum sum of absolute differences in heat levels and the minimum number of adjacent swaps required to achieve this maximum.

Example
Input
3
2
1 2
6
6 5 1 4 3 2
8
4 2 3 1 7 6 8 5
Output
1 0
17 6
31 6
Note

In the first test case, no workloads need to be swapped to reach the maximum difference of $$$1 = |1 - 2|$$$.

In the second test case, you can swap heat level $$$3$$$ to the very left. After 4 swaps, you have the heating configuration $$$3, 6, 5, 1, 4, 2$$$. Then you can swap $$$4$$$ with $$$2$$$ and $$$5$$$ with $$$1$$$, leaving $$$3, 6, 1, 5, 2, 4$$$. This permutation has a maximum sum of differences of $$$3 + 5 + 4 + 3 + 2 = 17$$$ after only 6 swaps. It can be proven that this is the maximum sum and the minimum number of adjacent swaps.