#include <bits/stdc++.h>
using namespace std;
int n;
vector<pair<long long, int>> x;
class segment {
 public:
  long long c;
  long long l, r;
  segment(long long c = 0, long long l = 0, long long r = 0)
      : c(c), l(l), r(r) {}
};
vector<segment> s;
vector<segment> update;
class cmp {
 public:
  bool operator()(segment A, segment B) { return A.c < B.c; }
};
int main() {
  cin >> n;
  while (n--) {
    long long a;
    cin >> a;
    if ((x.empty()) || (a < x.back().first))
      x.push_back({a, 1});
    else
      x.back().second++;
  }
  s.push_back(segment(0, 0, x[0].first - 1));
  int total = x[0].second;
  x.erase(x.begin());
  x.push_back({1, 1});
  long long maxupd = 1;
  for (auto p : x) {
    if (p.first <= maxupd) {
      maxupd = max(maxupd, s.back().r);
      for (auto x : update) s.push_back(x);
      update.clear();
      sort(s.begin(), s.end(), [](segment A, segment B) { return A.l > B.l; });
      priority_queue<segment, vector<segment>, cmp> q;
      while (!s.empty()) {
        auto p = s.back();
        if (!update.empty()) {
          while (update.back().r + 1 < p.l) {
            auto f = q.top();
            q.pop();
            if (f.r <= update.back().r) continue;
            update.push_back(segment(f.c, update.back().r + 1, f.r));
          }
        }
        s.pop_back();
        q.push(p);
        while ((!s.empty()) && (s.back().l == p.l)) {
          q.push(s.back());
          s.pop_back();
        }
        if (update.empty()) {
          update.push_back(q.top());
          q.pop();
        } else {
          if (q.top().c > update.back().c) {
            if (update.back().r > q.top().r)
              q.push(segment(update.back().c, q.top().r + 1, update.back().r));
            update.back().r = q.top().l - 1;
            update.push_back(q.top());
            q.pop();
          }
        }
      }
      while (update.back().r + 1 < maxupd) {
        auto f = q.top();
        q.pop();
        if (f.r <= update.back().r) continue;
        update.push_back(segment(f.c, update.back().r + 1, f.r));
      }
      maxupd = 1;
      for (auto p : update)
        if (s.empty() || (p.c != s.back().c))
          s.push_back(p);
        else
          s.back().r = p.r;
      update.clear();
    }
    while ((!s.empty()) && (s.back().r >= p.first)) {
      auto t = s.back();
      s.pop_back();
      if (t.l < p.first) {
        s.push_back(segment(t.c, t.l, p.first - 1));
        t.l = p.first;
      }
      if (t.r - t.l + 1 > p.first) t.l = t.r - p.first + 1;
      long long low = t.l % p.first;
      long long high = t.r % p.first;
      if (low <= high) {
        update.push_back(
            segment(t.c + (t.l - t.l % p.first) * total, low, high));
        maxupd = max(maxupd, high);
      } else {
        update.push_back(
            segment(t.c + (t.l - t.l % p.first) * total, low, p.first - 1));
        maxupd = p.first - 1;
        update.push_back(segment(t.c + (t.r - t.r % p.first) * total, 0, high));
      }
    }
    total += p.second;
  }
  long long ans = 0;
  for (auto p : s) ans = max(ans, p.c);
  for (auto p : update) {
    ans = max(ans, p.c);
  }
  cout << ans << '\n';
}

### 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;
int n;
vector<pair<long long, int>> x;
class segment {
 public:
  long long c;
  long long l, r;
  segment(long long c = 0, long long l = 0, long long r = 0)
      : c(c), l(l), r(r) {}
};
vector<segment> s;
vector<segment> update;
class cmp {
 public:
  bool operator()(segment A, segment B) { return A.c < B.c; }
};
int main() {
  cin >> n;
  while (n--) {
    long long a;
    cin >> a;
    if ((x.empty()) || (a < x.back().first))
      x.push_back({a, 1});
    else
      x.back().second++;
  }
  s.push_back(segment(0, 0, x[0].first - 1));
  int total = x[0].second;
  x.erase(x.begin());
  x.push_back({1, 1});
  long long maxupd = 1;
  for (auto p : x) {
    if (p.first <= maxupd) {
      maxupd = max(maxupd, s.back().r);
      for (auto x : update) s.push_back(x);
      update.clear();
      sort(s.begin(), s.end(), [](segment A, segment B) { return A.l > B.l; });
      priority_queue<segment, vector<segment>, cmp> q;
      while (!s.empty()) {
        auto p = s.back();
        if (!update.empty()) {
          while (update.back().r + 1 < p.l) {
            auto f = q.top();
            q.pop();
            if (f.r <= update.back().r) continue;
            update.push_back(segment(f.c, update.back().r + 1, f.r));
          }
        }
        s.pop_back();
        q.push(p);
        while ((!s.empty()) && (s.back().l == p.l)) {
          q.push(s.back());
          s.pop_back();
        }
        if (update.empty()) {
          update.push_back(q.top());
          q.pop();
        } else {
          if (q.top().c > update.back().c) {
            if (update.back().r > q.top().r)
              q.push(segment(update.back().c, q.top().r + 1, update.back().r));
            update.back().r = q.top().l - 1;
            update.push_back(q.top());
            q.pop();
          }
        }
      }
      while (update.back().r + 1 < maxupd) {
        auto f = q.top();
        q.pop();
        if (f.r <= update.back().r) continue;
        update.push_back(segment(f.c, update.back().r + 1, f.r));
      }
      maxupd = 1;
      for (auto p : update)
        if (s.empty() || (p.c != s.back().c))
          s.push_back(p);
        else
          s.back().r = p.r;
      update.clear();
    }
    while ((!s.empty()) && (s.back().r >= p.first)) {
      auto t = s.back();
      s.pop_back();
      if (t.l < p.first) {
        s.push_back(segment(t.c, t.l, p.first - 1));
        t.l = p.first;
      }
      if (t.r - t.l + 1 > p.first) t.l = t.r - p.first + 1;
      long long low = t.l % p.first;
      long long high = t.r % p.first;
      if (low <= high) {
        update.push_back(
            segment(t.c + (t.l - t.l % p.first) * total, low, high));
        maxupd = max(maxupd, high);
      } else {
        update.push_back(
            segment(t.c + (t.l - t.l % p.first) * total, low, p.first - 1));
        maxupd = p.first - 1;
        update.push_back(segment(t.c + (t.r - t.r % p.first) * total, 0, high));
      }
    }
    total += p.second;
  }
  long long ans = 0;
  for (auto p : s) ans = max(ans, p.c);
  for (auto p : update) {
    ans = max(ans, p.c);
  }
  cout << ans << '\n';
}

```