P8183 [USACO22FEB] Sleeping in Class B

题目描述

奶牛 Bessie 最近很高兴能够重返线下课堂！不幸的是，她的老师 Farmer John 讲课非常无聊，因此她经常在课堂上睡着。
Farmer John 注意到 Bessie 在课堂上没有专心听讲。他让班上的另一位学生 Elsie 记录 Bessie 在每节课上睡着的次数。总共有 $N$ 节课（$1 \leq N \leq 10^5$），Elsie 记录到 Bessie 在第 $i$ 节课上睡着了 $a_i$ 次（$0 \leq a_i \leq 10^6$）。所有课程中 Bessie 睡着的总次数不超过 $10^6$。

Elsie 对 Bessie 感到非常竞争，她希望让 Farmer John 觉得 Bessie 在每节课上睡着的次数是一致的——让问题看起来完全是 Bessie 的错，而与 Farmer John 有时无聊的讲课无关。Elsie 修改记录的唯一方式是将两节相邻的课合并。例如，如果 $a = [1,2,3,4,5]$，那么如果 Elsie 合并第二和第三节课，记录将变为 $[1,5,4,5]$。

请帮助 Elsie 计算她需要对记录进行的最少修改次数，以使记录中的所有数字相等。

输入格式

每个输入包含 $T$（$1 \leq T \leq 10$）个需要独立解决的测试用例。

第一行包含 $T$，表示测试用例的数量。接下来的 $T$ 组测试用例，每组由两行描述。每组的第一行包含 $N$，第二行包含 $a_1, a_2, \ldots, a_N$。

保证每个测试用例中，$a$ 的所有值之和不超过 $10^6$。同时，所有测试用例的 $N$ 之和不超过 $10^5$。

输出格式

请输出 $T$ 行，每行表示 Elsie 为使记录中的所有数字相等所需的最少修改次数。

输入输出样例 1

3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0

3
2
0

说明/提示

对于第一个测试用例，Elsie 可以通过 3 次修改将记录改为全为 $3$：

   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3

对于第二个测试用例，Elsie 可以通过 2 次修改将记录改为全为 $7$：

   2 2 3
-> 2 5
-> 7

对于最后一个测试用例，Elsie 不需要进行任何操作，因为记录已经由相同的数字组成。