Problem Description

Bessie wakes up on a strange planet. This planet has \( N \) ( \( 1 \le N \le 10^4 \) ) months, each with \( a_1, \ldots, a_N \) days ( \( 1 \le a_i \le 4 \cdot 10^9 \), all \( a_i \) are integers). Additionally, the planet has weeks, each consisting of \( L \) days, where \( L \) is a positive integer. Interestingly, Bessie knows the following:

• For the correct \( L \), each month has at least 4 weeks.
• For the correct \( L \), \( a_i \mod L \) has at most 3 different values.

Unfortunately, Bessie has forgotten what \( L \) is! Please help her by outputting the sum of all possible values of \( L \).

Note that the integers involved in this problem may require the use of 64-bit integer types (e.g., "long long" in C/C++).

Input Format

The first line of input contains an integer \( N \). The second line contains \( N \) space-separated integers \( a_1, \ldots, a_N \).

Output Format

Output a single integer, which is the sum of all possible values of \( L \).

Sample Input and Output

Sample Input #1

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

Sample Output #1

28

Sample Input #2

4
31 35 28 29

Sample Output #2

23

Notes/Hints

Sample Explanation 1

The possible values of \( L \) are \( 1, 2, 3, 4, 5, 6, \) and \( 7 \). For example, \( L = 7 \) is valid because each month has at least \( 4 \cdot 7 = 28 \) days, and the remainders of the days in each month when divided by 7 are all \( 0, 2, \) or \( 3 \).

Sample Explanation 2

The possible values of \( L \) are \( 1, 2, 3, 4, 6, \) and \( 7 \). For example, \( L = 6 \) is valid because each month has at least \( 4 \cdot 6 = 24 \) days, and the remainders of the days in each month when divided by 6 are all \( 1, 4, \) or \( 5 \).

Test Point Properties

• Test points \( 3-4 \): \( 1 \le a_i \le 10^6 \).
• Test points \( 5-14 \): No additional restrictions.

见题面 Input 部分

见题面 Output 部分