U269855 学习减法2

题目背景

2021 年陕西省赛签到题《兔子乘法》，100 支队伍有 96 支 AC，精准狙杀 4 个主办方队伍。还让前 10 的队伍有 8 支至少 WA 一次，区分度拉满，堪称签到题之王。

2022 年陕西省赛签到题《白浅妹妹的减法》，让 93 支队伍中的 7 支队伍爆零，分在 5 所不同学校（两个一本，两个 211，一个三本），雨露均沾。前 10 的队伍只有 4 支 WA 了签到，没有上一年表现好。

题目描述

白浅妹妹正在学习减法，她有 $n$ 个数字，她可以任选一个操作参数 $k(1 \leq k \leq n)$，选定 $k$ 的值之后就不能更改了。然后白浅妹妹可以进行无限次操作（至少一次），每次操作都是从这 $n$ 个数字中选择 $k$ 个位置不同的数字全部 -1，最终的目标是使得所有数字全部相等。

请问白浅妹妹可以选择的 $k$ 是多少？如果有多种可能的 $k$，请输出最大的一个。

输入格式

第一行输入一个正整数 $n(1 \leq n \leq 10^5)$，表示数字的个数。

接下来一行包含 $n$ 个正整数，分别表示白浅妹妹的每一个数字 $a_i(1 \leq a_i \leq 10^5)$。

输出格式

输出一行一个整数表示所有可能的 $k$ 中的最大值。

3
5 4 4

2

4
10 10 10 1

3

说明/提示

样例 1 说明：最多选择 $k=2$，然后进行两次操作，第一次将前两个数字 -1，三个数字变为 [4,3,4]，然后将第一个数字和第三个数字 -1，变为 [3,3,3]，此时所有数字全部相等。