← 返回题目列表

Codeforces · 2232/A

A. 收敛

中文机器翻译题面 查看原题

Alice 正在邀请她的朋友参加聚会吃蛋糕。然而,每个朋友可能不在同一个地方,所以大家必须先在同一个地点见面。

Alice 有 $$$n$$$ 个朋友,其中第 $$$i$$$ 位朋友位于 $$$a_i$$$ 位置。为了让每个人都在同一个地方,Alice 必须进行多次群组通话。不幸的是,信号很弱,Alice 一次只能呼叫 $$$2$$$ 其他人。

作为一个好人,爱丽丝不希望她的朋友走得太远。因此,对于包含第 $$$i$$$ 个朋友和第 $$$j$$$ 个朋友的每个群组通话,Alice 会告诉他们两个在 $$$\min(a_i, a_j)$$$ 和 $$$\max(a_i, a_j)$$$(含)之间的某个整数位置见面。之后,他们两人都会快速移动到该位置,以至于Alice在移动过程中无法进行任何群组通话。请注意,一旦这些朋友到达该位置,爱丽丝就可以再次呼叫他们。

聚会即将开始,因此 Alice 需要快速进行群组通话。帮助她找到需要拨打的最少群组通话次数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$) — Alice 的朋友数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 她朋友的位置。

输出

对于每个测试用例,输出她需要进行的最少群组通话次数,以便她的所有朋友都在同一位置。

示例

输入
复制

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

注意

在第一个测试用例中,组呼的最小数量为 2。使每个人都在同一位置的一种方法如下:

  • 呼叫第 $$$1$$$ 和第 $$$4$$$ 好友,并告诉他们移动到位置 $$$3$$$。他们的位置现在是$$$[3,2,3,3,5]$$$。
  • 呼叫第 $$$2$$$ 和第 $$$5$$$ 好友,并告诉他们移动到位置 $$$3$$$。他们的位置现在是 $$$[3, 3, 3, 3, 3]$$$。

在第二个测试用例中,群组呼叫的最小数量为 2。使每个人都在同一位置的一种方法如下:

  • 呼叫第 $$$1$$$ 和第 $$$4$$$ 好友,并告诉他们移动到位置 $$$1$$$。他们的位置现在是$$$[1, 1, 1, 1, 2]$$$。
  • 致电第 $$$4$$$ 和第 $$$5$$$ 好友,并告诉他们移动到位置 $$$1$$$。他们的位置现在是$$$[1, 1, 1, 1, 1]$$$。