题目描述

一艘观测船在一颗陌生星球上记录了 $N$ 个月的长度。第 $i$ 个月共有 $a_i$ 天。

这颗星球也有“周”的概念。一周有 $L$ 天，其中 $L$ 是正整数。观测船忘记了 $L$ 的具体值，但保留了两条信息：

• 对于正确的 $L$，每个月都至少包含 $4$ 个完整的周，即对所有 $i$ 都有 $4L\le a_i$；
• 对于正确的 $L$，集合$$\{a_i\bmod L\mid 1\le i\le N\}$$ 中至多有 $3$ 个不同的值。

请计算所有可能的 $L$ 的和。

答案可能较大，请使用 64 位整数类型。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

输出格式

输出一个整数，表示所有可能的 $L$ 的和。

样例

样例输入 1

12
31 28 31 30 31 30 31 31 30 31 30 31

样例输出 1

28

样例输入 2

4
31 35 28 29

样例输出 2

23

样例解释

对于样例 1，$L$ 的可能值为 $1,2,3,4,5,6,7$，它们的和为 $28$。

例如，当 $L=7$ 时，每个月至少有 $4\times 7=28$ 天，且所有月份天数模 $7$ 的余数只可能是 $0,2,3$。

对于样例 2，$L$ 的可能值为 $1,2,3,4,6,7$，它们的和为 $23$。

数据范围

对于所有测试数据，满足：

• $1\le N\le 10^4$；
• $1\le a_i\le 4\times 10^9$；
• 所有输入均为整数。

子任务

限制

单个测试点时间限制：1 s；全部 12 个测试点的时限总和为 12 s。

空间限制：512 MB。