该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $n$ 个数 $a_1,a_2,\ldots,a_n$。

单次操作内，你可以选择 $i\ne j$，并使得 $a_i$ 变为 $a_i-1$，同时 $a_j$ 变为 $a_j+1$。

求最小操作次数，使得，存在整数 $x>1$，满足这 $n$ 个数均能被 $x$ 整除。

注意：任意时刻，你均需要保证 $a_i$ 非负。

提示：$0$ 能被任何正整数整除；可以证明，一定有解。

输入格式

第一行一个整数 $n$，意义如题述。

第二行 $n$ 个数，表示 $a_1,a_2,\ldots,a_n$。

输出格式

仅一行一个数，表示答案。

样例

输入样例 1

5
1 2 3 4 5

输出样例 1

2

样例 1 说明

• 初始 $a$ 为 $[1,2,3,4,5]$；
• 第一次，选择 $i=1,j=2$，$a$ 变为 $[0,3,3,4,5]$；
• 第二次，选择 $i=4,j=5$，$a$ 变为 $[0,3,3,3,6]$；
• 此时，取 $x=3$，符合要求。

可以证明，$2$ 是最小的操作次数。

输入样例 2

2
5 7

输出样例 2

1

数据规模与约定

对于 $100\%$ 的数据，$2\le n \le 5\times10^5$，$1\le a_i\le 10^5$。