USACO 2022 February Contest, Bronze
Problem 1. Sleeping in Class
Contest has ended.
Log in to allow submissions in analysis mode
Farmer John 注意到 Bessie 在课堂上没有专心听讲。他让班上的另一名学生 Elsie 记录 Bessie 在一节课中睡着的次数。总共有 $N$ 个课时（$1\le N\le 10^5$），Elsie 记录下 Bessie 在第 $i$ 个课时睡着了 $a_i$ 次（$0\le a_i\le 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\le T\le 10$）个需要独立求解的子测试用例。输入的第一行包含 $T$，为需要求解的子测试用例的数量。以下是 $T$ 个子测试用例，每个子测试用例包含两行。第一行包含 $N$，第二行包含 $a_1,a_2,\ldots,a_N$。
输入保证在每个子测试用例中，$a$ 中所有数之和不超过 $10^6$。同时输入保证所有子测试用例的 $N$ 之和不超过 $10^5$。
输出格式（输出至终端 / 标准输出）：
输出 $T$ 行，对每个子测试用例输出 Elsie 可以令记录中的所有数相等所需进行的最小修改次数。
输入样例：
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 无需执行任何操作；记录已经由相等的数组成。
供题：Jesse Choe