You are given a sequence of integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$. Let , and for $1 ≤ *i* < *n*$. Here, denotes the modulus operation. Find the maximum value of $*f*(*x*, 1)$ over all nonnegative integers $*x*$.

Input

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

The second lines contains $*n*$ integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ ($1 ≤ *a*_{*i*} ≤ 10^{13}$) — the elements of the sequence.

Output

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

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$.