G. Syl 和序列操作
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Syl 有一个长度为 $$$n$$$ 的整数序列 $$${a_i}$$$，她每次可以选择一个下标 $$$i(1 \le i \le n)$$$，并从下列三种操作选择一种进行：

  • 将 $$$a_i$$$ 变为 $$$a_i+1$$$ 或 $$$a_i-1$$$。
  • 对所有 $$$j \gt i$$$ 且 $$$a_j \gt a_i$$$ 的 $$$j$$$，将 $$$a_j$$$ 变为 $$$a_j-1$$$。
  • 对所有 $$$j \lt i$$$ 且 $$$a_j \lt a_i$$$ 的 $$$j$$$，将 $$$a_j$$$ 变为 $$$a_j+1$$$。

现在 Syl 觉得她的序列太不整齐了，于是想通过上面三种操作将序列的所有数字变得相同。请你帮助她算一算，最少需要多少次操作才能满足 Syl 的愿望呢？

Input

第一行，一个整数 $$$t$$$ $$$(1\le t\le 10^5)$$$，表示测试数据的组数。

对于每组测试数据，第一行输入一个整数 $$$n$$$ $$$(1\le n\le 10^5)$$$，表示序列长度；第二行包含 $$$n$$$ 个整数 $$$a_i$$$ $$$(-10^9\le a_i \le 10^9)$$$。

保证所有测试数据的 $$$n$$$ 之和 $$$\sum n\le 10^5$$$。

Output

对每组测试数据，输出一个整数，表示最少能使得序列数字全部相同的操作数。

Example
Input
2
5
1 2 3 4 5
5
5 4 3 2 1
Output
4
6