#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 200000;
typedef struct G {
  long long len;
  map<long long, long long> hor, ver;
  void init(long long _len) {
    len = _len;
    hor.clear();
    ver.clear();
    hor[0] = 0;
    ver[0] = 0;
  }
  void resize(long long _len) {
    len = _len;
    auto it = hor.lower_bound(len);
    while (it != hor.end()) {
      ver.erase(it->second);
      auto prv = it++;
      hor.erase(prv);
    }
  }
  void update(long long x, long long y) {
    long long sx, py, ny, nx;
    auto it = ver.lower_bound(y);
    py = it == ver.end() ? LLONG_MAX : it->first;
    if (it == ver.begin()) return;
    --it;
    sx = it->second;
    if (sx > x) return;
    while (it != ver.begin() && it->second <= x) {
      ny = it->first;
      hor.erase(it->second);
      auto prv = it--;
      ver.erase(prv);
    }
    if (it == ver.begin() && it->second <= x) {
      ny = it->first;
      hor.erase(it->second);
      ver.erase(it);
      nx = len;
    } else
      nx = it->second;
    if (y != py) hor[sx] = y, ver[y] = sx;
    if (x + 1 != nx) hor[x + 1] = ny, ver[ny] = x + 1;
  }
  vector<pair<long long, long long> > getfrom(long long x) {
    vector<pair<long long, long long> > ret;
    auto it = hor.lower_bound(x);
    if (it == hor.end() || it->first > x) --it;
    ret.push_back(make_pair(x, it->second));
    ++it;
    while (it != hor.end()) {
      ret.push_back(make_pair(it->first, it->second));
      ++it;
    }
    ret.push_back(make_pair(len, 0LL));
    return ret;
  }
  long long calc(int mlt) {
    long long ret = LLONG_MIN;
    for (auto it = hor.begin(); it != hor.end(); ++it) {
      long long y = it->second;
      auto nxt = it;
      ++nxt;
      long long x = nxt == hor.end() ? len - 1 : nxt->first - 1;
      long long cur = y + x * mlt;
      if (cur > ret) ret = cur;
    }
    return ret;
  }
  void print(int a) {
    printf("hor%d:", a);
    for (auto it = hor.begin(); it != hor.end(); ++it)
      printf(" (%lld,%lld)", it->first, it->second);
    puts("");
    printf("ver%d:", a);
    for (auto it = ver.begin(); it != ver.end(); ++it)
      printf(" (%lld,%lld)", it->first, it->second);
    puts("");
  }
} G;
int n;
long long a[MAXN];
G g;
void run() {
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) scanf("%lld", &a[i]);
  g.init(a[0]);
  for (int i = (1); i < (n); ++i)
    if (a[i] < g.len) {
      vector<pair<long long, long long> > p = g.getfrom(a[i]);
      g.resize(a[i]);
      for (int j = (1); j < (((int)(p).size())); ++j) {
        long long px = p[j - 1].first, x = p[j].first - 1, y = p[j - 1].second;
        g.update(x % a[i], y + (x / a[i]) * i * a[i]);
        if (px / a[i] != x / a[i])
          g.update(a[i] - 1, y + ((x / a[i]) - 1) * i * a[i]);
      }
    }
  long long ret = g.calc(n);
  printf("%lld\n", ret);
}
int main() {
  run();
  return 0;
}

### Prompt

Generate 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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 200000;
typedef struct G {
  long long len;
  map<long long, long long> hor, ver;
  void init(long long _len) {
    len = _len;
    hor.clear();
    ver.clear();
    hor[0] = 0;
    ver[0] = 0;
  }
  void resize(long long _len) {
    len = _len;
    auto it = hor.lower_bound(len);
    while (it != hor.end()) {
      ver.erase(it->second);
      auto prv = it++;
      hor.erase(prv);
    }
  }
  void update(long long x, long long y) {
    long long sx, py, ny, nx;
    auto it = ver.lower_bound(y);
    py = it == ver.end() ? LLONG_MAX : it->first;
    if (it == ver.begin()) return;
    --it;
    sx = it->second;
    if (sx > x) return;
    while (it != ver.begin() && it->second <= x) {
      ny = it->first;
      hor.erase(it->second);
      auto prv = it--;
      ver.erase(prv);
    }
    if (it == ver.begin() && it->second <= x) {
      ny = it->first;
      hor.erase(it->second);
      ver.erase(it);
      nx = len;
    } else
      nx = it->second;
    if (y != py) hor[sx] = y, ver[y] = sx;
    if (x + 1 != nx) hor[x + 1] = ny, ver[ny] = x + 1;
  }
  vector<pair<long long, long long> > getfrom(long long x) {
    vector<pair<long long, long long> > ret;
    auto it = hor.lower_bound(x);
    if (it == hor.end() || it->first > x) --it;
    ret.push_back(make_pair(x, it->second));
    ++it;
    while (it != hor.end()) {
      ret.push_back(make_pair(it->first, it->second));
      ++it;
    }
    ret.push_back(make_pair(len, 0LL));
    return ret;
  }
  long long calc(int mlt) {
    long long ret = LLONG_MIN;
    for (auto it = hor.begin(); it != hor.end(); ++it) {
      long long y = it->second;
      auto nxt = it;
      ++nxt;
      long long x = nxt == hor.end() ? len - 1 : nxt->first - 1;
      long long cur = y + x * mlt;
      if (cur > ret) ret = cur;
    }
    return ret;
  }
  void print(int a) {
    printf("hor%d:", a);
    for (auto it = hor.begin(); it != hor.end(); ++it)
      printf(" (%lld,%lld)", it->first, it->second);
    puts("");
    printf("ver%d:", a);
    for (auto it = ver.begin(); it != ver.end(); ++it)
      printf(" (%lld,%lld)", it->first, it->second);
    puts("");
  }
} G;
int n;
long long a[MAXN];
G g;
void run() {
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) scanf("%lld", &a[i]);
  g.init(a[0]);
  for (int i = (1); i < (n); ++i)
    if (a[i] < g.len) {
      vector<pair<long long, long long> > p = g.getfrom(a[i]);
      g.resize(a[i]);
      for (int j = (1); j < (((int)(p).size())); ++j) {
        long long px = p[j - 1].first, x = p[j].first - 1, y = p[j - 1].second;
        g.update(x % a[i], y + (x / a[i]) * i * a[i]);
        if (px / a[i] != x / a[i])
          g.update(a[i] - 1, y + ((x / a[i]) - 1) * i * a[i]);
      }
    }
  long long ret = g.calc(n);
  printf("%lld\n", ret);
}
int main() {
  run();
  return 0;
}

```