题解

题目描述

给定一个长度为$n$的数组$a = [a_1, a_2, \dots, a_n]$，一次操作可以选择数组中的一个数，然后将其移除，剩余元素保持原顺序依次拼接。希望经过若干次操作后，使得数组中所有非空子数组的平均值均相同。
子数组的定义为从原数组中连续选取的一段元素（可以全选也可以部分选）。

题目分析与思路

题目内容

给定一个长度为 $n$ 的数组 $a$ ，定义一次操作

• 选择数组中的一个数，然后把这个数从数组中移除，其余元素按照原有顺序从前到后依次拼接，

现在她想要知道，自己最少需要操作几次，才能使得数组中所有非空学数组的平均值均相同。

子数组为从原数组中,连续的选择一段元素(可以全选，可以不选)得到的新数组。

输入描述

第一行输入一个整数$n(1≦n≦2×10^5)$,表示数组长度。

第二行输入$n$个整数$a_1,a_2,...,a_n (1≦a_i≦10^9)$代表数组。

输出描述

一个整数，表示最少操作次数。

样例1

输入

3
1 2 3

输出

2

说明

删除任意两个元素后，数组只剩下一个元素，此时只有一个非空子数组，一定满足题意。

样例2

输入

5
12111

输出

1

说明

唯一的方案是将第二个元素删除。