Mod Mod Mod

Description:

Input:

The first line contains a single integer n (1 ≤ n ≤ 200000) — the length of the sequence.

The second lines contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10¹³) — the elements of the sequence.

Output:

Output a single integer — the maximum value of f(x, 1) over all nonnegative integers x.

Sample Input:

2
10 5

Sample Output:

13

Sample Input:

5
5 4 3 2 1

Sample Output:

6

Sample Input:

4
5 10 5 10

Sample Output:

16

Note:

In the first example you can choose, for example, x = 19.

In the second example you can choose, for example, x = 3 or x = 2.