ConvergenceAI (CI翻译)
Alice is inviting her friends to a party to eat cakes. However, each friend may not be at the same place, so everyone has to meet up at the same location first.
Alice has $n$ friends, where the $i$-th friend is at position $a_i$. To make everyone be at the same place, Alice has to make multiple group calls. Unfortunately, the signal is weak, and Alice can only call $2$ other people at a time.
Being a good person, Alice doesn't want her friends to walk too far. So, for each group call containing the $i$-th friend and the $j$-th friend, Alice will tell both of them to meet at some integer location between $\min(a_i, a_j)$ and $\max(a_i, a_j)$ inclusive. After that, both of them will move to that location so quickly that Alice cannot make any group call during their movement. Please note that Alice can call these friends again once they reach that location.
The party is starting soon, so Alice needs to make group calls fast. Help her find the minimum number of group calls she needs to make.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.
The first line of each test case contains an integer $n$ ($2 \leq n \leq 100$) — the number of friends Alice has.
The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 10^9$) — the locations of her friends.
Output
For each test case, output the minimum number of group calls she needs to make in order for all of her friends to be in the same location.
Note
In the first test case, the minimum number of group calls is 2. One way to make everyone at the same location is as follows:
- Call the
$1$-st and$4$-th friend and tell them to move to location$3$. Their locations are now$[3, 2, 3, 3, 5]$. - Call the
$2$-nd and$5$-th friend and tell them to move to location$3$. Their locations are now$[3, 3, 3, 3, 3]$.
In the second test case, the minimum number of group calls is 2. One way to make everyone at the same location is as follows:
- Call the
$1$-st and$4$-th friend and tell them to move to location$1$. Their locations are now$[1, 1, 1, 1, 2]$. - Call the
$4$-th and$5$-th friend and tell them to move to location$1$. Their locations are now$[1, 1, 1, 1, 1]$.
{"titleZh":"收敛","bodyZh":"## 题目描述\n\nAlice 邀请她的朋友们来参加一个吃蛋糕的聚会。然而，每位朋友可能不在同一个地方，因此大家必须先在同一地点集合。\n\nAlice 有 $n$ 位朋友，其中第 $i$ 位朋友位于位置 $a_i$。为了让所有人到达同一地点，Alice 需要进行多次群呼。不幸的是，信号很弱，Alice 每次只能同时呼叫 $2$ 个人。\n\nAlice 是个善良的人，不希望她的朋友走太远。因此，对于一次包含第 $i$ 位和第 $j$ 位朋友的群呼，Alice 会让他们两人前往 $\min(a_i, a_j)$ 和 $\max(a_i, a_j)$ 之间（包含端点）的某个整数位置。随后，两人会非常迅速地移动到该位置，以至于 Alice 在他们移动期间无法进行任何群呼。请注意，当这些朋友到达该位置后，Alice 可以再次呼叫他们。\n\n聚会马上就要开始了，因此 Alice 需要快速完成群呼。请帮助她找出使所有朋友到达同一位置所需的最少群呼次数。\n\n## 输入格式\n\n每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。接下来描述各个测试用例。\n\n每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 100$）——Alice 拥有的朋友数量。\n\n每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\\ldots,a_n$（$1 \leq a_i \leq 10^9$）——朋友们所在的位置。\n\n## 输出格式\n\n对于每个测试用例，输出使所有朋友位于同一位置所需的最少群呼次数。\n\n## 说明\n\n在第一个测试用例中，最少群呼次数为 2。一种让所有人到达同一位置的方法如下：\n\n- 呼叫第 $1$ 位和第 $4$ 位朋友，让他们移动到位置 $3$。此时他们的位置为 $[3, 2, 3, 3, 5]$。\n- 呼叫第 $2$ 位和第 $5$ 位朋友，让他们移动到位置 $3$。此时他们的位置为 $[3, 3, 3, 3, 3]$。\n\n在第二个测试用例中，最少群呼次数为 2。一种让所有人到达同一位置的方法如下：\n\n- 呼叫第 $1$ 位和第 $4$ 位朋友，让他们移动到位置 $1$。此时他们的位置为 $[1, 1, 1, 1, 2]$。\n- 呼叫第 $4$ 位和第 $5$ 位朋友，让他们移动到位置 $1$。此时他们的位置为 $[1, 1, 1, 1, 1]$。"}AI (CI翻译)
样例
4
5
1 2 3 4 5
5
1 1 1 2 2
11
3 1 4 1 5 9 2 6 5 3 5
5
1 2 2 2 2
2
2
5
1
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。