#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= f;
}
const int N = 400000;
int n;
long long a[N];
map<long long, long long> f[N];
struct node {
  int l, r;
  long long mn;
} tree[N << 2];
inline void update(int k) {
  tree[k].mn = min(tree[(k << 1)].mn, tree[(k << 1 | 1)].mn);
}
inline void build(int k, int l, int r) {
  tree[k].l = l;
  tree[k].r = r;
  if (l == r) {
    tree[k].mn = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build((k << 1), l, mid);
  build((k << 1 | 1), mid + 1, r);
  update(k);
}
inline int query(int i, long long r) {
  int u;
  for (u = 1; tree[u].l != tree[u].r;
       u = i <= tree[(u << 1)].r ? (u << 1) : (u << 1 | 1))
    ;
  while (u > 1) {
    int fa = u >> 1;
    if ((fa << 1 | 1) == u) {
      u = fa;
      continue;
    }
    u = fa;
    if (tree[(u << 1 | 1)].mn <= r) {
      u = (u << 1 | 1);
      for (; tree[u].l != tree[u].r;)
        if (tree[(u << 1)].mn <= r)
          u = (u << 1);
        else
          u = (u << 1 | 1);
      return tree[u].l;
    }
  }
  return n + 1;
}
int main() {
  read(n);
  for (register int i = 1; i <= n; i++) read(a[i]);
  build(1, 1, n);
  f[1][a[1] - 1] = 0;
  for (register int i = 1; i <= n - 1; i++)
    while (!f[i].empty()) {
      map<long long, long long>::iterator it = f[i].begin();
      f[i].erase(it);
      long long r = (*it).first, k = (*it).second;
      if (r < a[i + 1]) {
        int t = query(i + 1, r) - 1;
        if (f[t].count(r)) {
          if (k > f[t][r]) f[t][r] = k;
        } else
          f[t][r] = k;
      } else {
        long long v = k + 1LL * i * (a[i + 1] * (r / a[i + 1]));
        if (f[i + 1].count(r % a[i + 1])) {
          if (v > f[i + 1][r % a[i + 1]]) f[i + 1][r % a[i + 1]] = v;
        } else
          f[i + 1][r % a[i + 1]] = v;
        if (f[i + 1].count(a[i + 1] - 1)) {
          if (v - i * a[i + 1] > f[i + 1][a[i + 1] - 1])
            f[i + 1][a[i + 1] - 1] = v - i * a[i + 1];
        } else
          f[i + 1][a[i + 1] - 1] = v - i * a[i + 1];
      }
    }
  long long ans = 0;
  while (!f[n].empty()) {
    map<long long, long long>::iterator it = f[n].begin();
    long long r = (*it).first, k = (*it).second;
    f[n].erase(it);
    {
      if (k + n * r > ans) ans = k + n * r;
    };
  }
  printf("%lld", ans);
  return 0;
}

### Prompt

Your task is to create 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>
using namespace std;
template <class T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= f;
}
const int N = 400000;
int n;
long long a[N];
map<long long, long long> f[N];
struct node {
  int l, r;
  long long mn;
} tree[N << 2];
inline void update(int k) {
  tree[k].mn = min(tree[(k << 1)].mn, tree[(k << 1 | 1)].mn);
}
inline void build(int k, int l, int r) {
  tree[k].l = l;
  tree[k].r = r;
  if (l == r) {
    tree[k].mn = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build((k << 1), l, mid);
  build((k << 1 | 1), mid + 1, r);
  update(k);
}
inline int query(int i, long long r) {
  int u;
  for (u = 1; tree[u].l != tree[u].r;
       u = i <= tree[(u << 1)].r ? (u << 1) : (u << 1 | 1))
    ;
  while (u > 1) {
    int fa = u >> 1;
    if ((fa << 1 | 1) == u) {
      u = fa;
      continue;
    }
    u = fa;
    if (tree[(u << 1 | 1)].mn <= r) {
      u = (u << 1 | 1);
      for (; tree[u].l != tree[u].r;)
        if (tree[(u << 1)].mn <= r)
          u = (u << 1);
        else
          u = (u << 1 | 1);
      return tree[u].l;
    }
  }
  return n + 1;
}
int main() {
  read(n);
  for (register int i = 1; i <= n; i++) read(a[i]);
  build(1, 1, n);
  f[1][a[1] - 1] = 0;
  for (register int i = 1; i <= n - 1; i++)
    while (!f[i].empty()) {
      map<long long, long long>::iterator it = f[i].begin();
      f[i].erase(it);
      long long r = (*it).first, k = (*it).second;
      if (r < a[i + 1]) {
        int t = query(i + 1, r) - 1;
        if (f[t].count(r)) {
          if (k > f[t][r]) f[t][r] = k;
        } else
          f[t][r] = k;
      } else {
        long long v = k + 1LL * i * (a[i + 1] * (r / a[i + 1]));
        if (f[i + 1].count(r % a[i + 1])) {
          if (v > f[i + 1][r % a[i + 1]]) f[i + 1][r % a[i + 1]] = v;
        } else
          f[i + 1][r % a[i + 1]] = v;
        if (f[i + 1].count(a[i + 1] - 1)) {
          if (v - i * a[i + 1] > f[i + 1][a[i + 1] - 1])
            f[i + 1][a[i + 1] - 1] = v - i * a[i + 1];
        } else
          f[i + 1][a[i + 1] - 1] = v - i * a[i + 1];
      }
    }
  long long ans = 0;
  while (!f[n].empty()) {
    map<long long, long long>::iterator it = f[n].begin();
    long long r = (*it).first, k = (*it).second;
    f[n].erase(it);
    {
      if (k + n * r > ans) ans = k + n * r;
    };
  }
  printf("%lld", ans);
  return 0;
}

```