Bessie’s Mysterious Week Length

Bessie wakes up on a strange planet which has N months. The i-th month has a_i days. In addition, this planet has weeks of an unknown length L (a positive integer). Bessie knows that for the correct week length L the following conditions hold:

1. Every month has at least 4 complete weeks. In other words, for every i we have \(a_i \ge 4L\).
2. The remainders of the month lengths when divided by L take at most 3 distinct values, i.e. \(|\{a_i \bmod L : 1 \le i \le N\}| \le 3\).

Your task is to help Bessie by computing the sum of all possible values of L that satisfy the above conditions.

Note: Since the integers involved can be very large, you may need to use 64-bit integer types (for example, long long in C/C++).

inputFormat

The first line contains one integer N (\(1 \le N \le 10^4\)). The second line contains N space-separated integers \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 4 \cdot 10^9\)); these denote the number of days in each month.

outputFormat

Output a single integer which is the sum of all possible week lengths L that satisfy the conditions.

sample

1
20

15