#include <bits/stdc++.h>
using namespace std;
const int _ = 1e2;
const int maxn = 2e5 + _;
long long a[maxn];
int s[maxn];
struct node {
  int t;
  long long p, d;
  node() {}
  node(int T, long long P, long long D) { t = T, p = P, d = D; }
  friend bool operator<(node n1, node n2) {
    return n1.p == n2.p ? n1.t < n2.t : n1.p > n2.p;
  }
  friend bool operator>(node n1, node n2) {
    return n1.p == n2.p ? n1.t > n2.t : n1.p < n2.p;
  }
};
set<node> S, T;
void upd(node tno) {
  set<node>::iterator k1 = S.find(tno), k2 = T.find(tno);
  if ((k1 == S.end() || k1->d < tno.d) && (k2 == T.end() || k2->d < tno.d)) {
    if (k2 != T.end()) {
      T.erase(k2);
    }
    T.insert(tno);
  }
}
set<node>::iterator it, ut;
int main() {
  int n, tp = 0;
  long long x;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &x);
    if (tp != 0 && a[tp] < x)
      s[tp]++;
    else
      a[++tp] = x, s[tp] = 1;
  }
  n = tp;
  for (int i = 1; i <= n; i++) s[i] += s[i - 1];
  S.insert(node(1, a[1] - 1, 0));
  for (int i = 2; i <= n; i++) {
    for (it = S.begin();; it++) {
      if (it != S.begin()) {
        S.erase(ut);
      }
      if (it->p < a[i] || it == S.end()) break;
      node tno = *it, ntno;
      tno.d += (s[i - 1] - s[tno.t - 1]) * tno.p;
      ntno = node(i, tno.p % a[i], tno.d);
      upd(ntno);
      ntno = node(i, a[i] - 1,
                  tno.d - s[i - 1] * (tno.p - tno.p / a[i] * a[i] + 1));
      upd(ntno);
      ut = it;
    }
    for (it = T.begin(); it != T.end(); it++) {
      ut = S.find(*it);
      if (ut != S.end()) S.erase(ut);
      S.insert(*it);
    }
    T.clear();
  }
  long long ans = 0;
  for (it = S.begin(); it != S.end(); it++) {
    node tno = *it;
    tno.d += (s[n] - s[tno.t - 1]) * tno.p;
    ans = max(ans, tno.d);
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Create a solution in cpp for 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;
const int _ = 1e2;
const int maxn = 2e5 + _;
long long a[maxn];
int s[maxn];
struct node {
  int t;
  long long p, d;
  node() {}
  node(int T, long long P, long long D) { t = T, p = P, d = D; }
  friend bool operator<(node n1, node n2) {
    return n1.p == n2.p ? n1.t < n2.t : n1.p > n2.p;
  }
  friend bool operator>(node n1, node n2) {
    return n1.p == n2.p ? n1.t > n2.t : n1.p < n2.p;
  }
};
set<node> S, T;
void upd(node tno) {
  set<node>::iterator k1 = S.find(tno), k2 = T.find(tno);
  if ((k1 == S.end() || k1->d < tno.d) && (k2 == T.end() || k2->d < tno.d)) {
    if (k2 != T.end()) {
      T.erase(k2);
    }
    T.insert(tno);
  }
}
set<node>::iterator it, ut;
int main() {
  int n, tp = 0;
  long long x;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &x);
    if (tp != 0 && a[tp] < x)
      s[tp]++;
    else
      a[++tp] = x, s[tp] = 1;
  }
  n = tp;
  for (int i = 1; i <= n; i++) s[i] += s[i - 1];
  S.insert(node(1, a[1] - 1, 0));
  for (int i = 2; i <= n; i++) {
    for (it = S.begin();; it++) {
      if (it != S.begin()) {
        S.erase(ut);
      }
      if (it->p < a[i] || it == S.end()) break;
      node tno = *it, ntno;
      tno.d += (s[i - 1] - s[tno.t - 1]) * tno.p;
      ntno = node(i, tno.p % a[i], tno.d);
      upd(ntno);
      ntno = node(i, a[i] - 1,
                  tno.d - s[i - 1] * (tno.p - tno.p / a[i] * a[i] + 1));
      upd(ntno);
      ut = it;
    }
    for (it = T.begin(); it != T.end(); it++) {
      ut = S.find(*it);
      if (ut != S.end()) S.erase(ut);
      S.insert(*it);
    }
    T.clear();
  }
  long long ans = 0;
  for (it = S.begin(); it != S.end(); it++) {
    node tno = *it;
    tno.d += (s[n] - s[tno.t - 1]) * tno.p;
    ans = max(ans, tno.d);
  }
  printf("%lld\n", ans);
  return 0;
}

```