Cowlendar

Time limit2sMemory limit1024 MB

Summary

Given month lengths a_i, find the sum of all week lengths L where every month is at least 4 weeks and a_i mod L takes at most 3 values.

Level: Medium7 of 10
Topics: Number theory, Math, Hash map
Solved: No attempts yet

Problem

Bessie has woken up on a strange planet. This planet has $N$ ( $1\le N\le 10^4$ ) months, with $a_1, \ldots, a_N$ days, respectively ( $1\leq a_i \leq 4 \cdot 10^9$ , all $a_i$ are integers). The planet also has weeks. Each week is $L$ days, where $L$ is a positive integer.

Bessie knows the following about the correct $L$ :

Each month is at least $4$ weeks long.
There are at most $3$ distinct values of $a_i \bmod L$ .

Bessie has forgotten what $L$ is. Print the sum of all possible values of $L$ .

The large integers in this problem may require 64-bit integer types (for example, "long long" in C/C++).

Input

The first line contains a single integer $N$ . The second line contains $N$ space-separated integers $a_1, \ldots, a_N$ .

Output

Print a single integer, the sum of all possible values of $L$ .

Examples2

Example 1

Input

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

Expected output

Example 2
Input
```
4
31 35 28 29
```
Expected output
```
23
```