seuOJ563 - Syl 和序列操作

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：1024 MiB
• 题目标签：夏季, 2025

题目描述

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

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

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

输入格式

第一行，一个整数 $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$。

输出格式

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

样例

输入样例

2
5
1 2 3 4 5
5
5 4 3 2 1

输出样例

4
6