-->

Problem Statement-

You are given a sequence ${A}_{1},{A}_{2},\dots ,{A}_{N}$. Find the maximum value of the expression $|{A}_{x}-{A}_{y}|+|{A}_{y}-{A}_{z}|+|{A}_{z}-{A}_{x}|$ over all triples of pairwise distinct valid indices $\left(x,y,z\right)$.

Input

• The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• The first line of each test case contains a single integer $N$.
• The second line contains $N$ space-separated integers ${A}_{1},{A}_{2},\dots ,{A}_{N}$.

Output

For each test case, print a single line containing one integer ― the maximum value of $|{A}_{x}-{A}_{y}|+|{A}_{y}-{A}_{z}|+|{A}_{z}-{A}_{x}|$.

Constraints

• $1\le T\le 5$
• $3\le N\le {10}^{5}$
• $|{A}_{i}|\le {10}^{9}$ for each valid $i$

Subtask #1 (30 points): $N\le 500$

Subtask #2 (70 points): original constraints

Example Input

3
3
2 7 5
3
3 3 3
5
2 2 2 2 5


Example Output

10
0
6


Explanation

Example case 1: The value of the expression is always $10$. For example, let $x=1$$y=2$ and $z=3$, then it is $|2-7|+|7-5|+|5-2|=5+2+3=10$.

Example case 2: Since all values in the sequence are the same, the value of the expression is always $0$.

Example case 3: One optimal solution is $x=1$$y=2$ and $z=5$, which gives $|2-2|+|2-5|+|5-2|=0+3+3=6$.

Solution-

Hint - Sort the array.

Solution will be posted anytime soon stay connect .

Must join Telegram channel