#include <bits/stdc++.h>
const int maxn = 222222;
int n;
long long a[maxn], f[maxn];
long long In() {
  register int c, f;
  register long long s;
  for (; c = getchar(), c != '-' && !isdigit(c);)
    ;
  for (s = (f = c == '-') ? 0 : c - '0'; c = getchar(), isdigit(c);)
    s = s * 10 + c - '0';
  return f ? -s : s;
}
long long dmax(register long long a, register long long b) {
  return a > b ? a : b;
}
long long qry(register int x, register long long v) {
  if (!v) return -1ll << 60;
  if (v >= a[x + 1]) {
    register long long d = v / a[x + 1];
    return dmax(f[x + 1] + a[x + 1] * (d - 1) * x,
                qry(x + 1, v % a[x + 1]) + a[x + 1] * d * x);
  }
  register int ll = x + 1, rr = n + 1;
  for (register int mm; mm = (ll + rr + 1) >> 1, ll < rr;
       v >= a[mm] ? rr = mm - 1 : ll = mm)
    ;
  return qry(ll, v);
}
int main() {
  n = In();
  for (register int i = 1; i <= n; ++i)
    a[i] = In(), i > 1 && a[i] > a[i - 1] ? a[i] = a[i - 1] : 0;
  a[n + 1] = 1;
  for (register int i = n; i >= 1; --i) f[i] = qry(i, a[i]);
  printf("%lld\n", f[1]);
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

You are given a sequence of integers a1, a2, ..., an. Let <image>, and <image> for 1 ≤ i < n. Here, <image> 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 a1, a2, ..., an (1 ≤ ai ≤ 1013) — the elements of the sequence.

Output

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

Examples

Input

2
10 5


Output

13


Input

5
5 4 3 2 1


Output

6


Input

4
5 10 5 10


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.

### Response

```cpp
#include <bits/stdc++.h>
const int maxn = 222222;
int n;
long long a[maxn], f[maxn];
long long In() {
  register int c, f;
  register long long s;
  for (; c = getchar(), c != '-' && !isdigit(c);)
    ;
  for (s = (f = c == '-') ? 0 : c - '0'; c = getchar(), isdigit(c);)
    s = s * 10 + c - '0';
  return f ? -s : s;
}
long long dmax(register long long a, register long long b) {
  return a > b ? a : b;
}
long long qry(register int x, register long long v) {
  if (!v) return -1ll << 60;
  if (v >= a[x + 1]) {
    register long long d = v / a[x + 1];
    return dmax(f[x + 1] + a[x + 1] * (d - 1) * x,
                qry(x + 1, v % a[x + 1]) + a[x + 1] * d * x);
  }
  register int ll = x + 1, rr = n + 1;
  for (register int mm; mm = (ll + rr + 1) >> 1, ll < rr;
       v >= a[mm] ? rr = mm - 1 : ll = mm)
    ;
  return qry(ll, v);
}
int main() {
  n = In();
  for (register int i = 1; i <= n; ++i)
    a[i] = In(), i > 1 && a[i] > a[i - 1] ? a[i] = a[i - 1] : 0;
  a[n + 1] = 1;
  for (register int i = n; i >= 1; --i) f[i] = qry(i, a[i]);
  printf("%lld\n", f[1]);
  return 0;
}

```