#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  int n;
  cin >> n;
  vector<long long> v, kf;
  for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    if (i > 0 && v.back() <= x)
      kf.back() = i + 1;
    else {
      v.push_back(x);
      kf.push_back(i + 1);
    }
  }
  n = v.size();
  set<pair<long long, long long> > st;
  st.insert(make_pair(v[0] - 1, 0));
  for (int i = 0; i < n; i++)
    if (i > 0) {
      vector<pair<long long, long long> > change;
      pair<long long, long long> ac = make_pair(-1, -1);
      while (st.size() > 0 && st.rbegin()->first >= v[i]) {
        pair<long long, long long> p = *st.rbegin();
        st.erase(p);
        long long k = p.first / v[i];
        long long d = (k - 1) * v[i] * kf[i - 1] + p.second;
        if (ac.second < d) ac = make_pair(v[i] - 1, d);
        change.push_back(
            make_pair(p.first - k * v[i], p.second + k * v[i] * kf[i - 1]));
      }
      for (int i = 0; i < change.size(); i++) st.insert(change[i]);
      st.insert(ac);
    }
  long long ans = 0;
  for (auto j = st.begin(); j != st.end(); j++) {
    ans = max(ans, j->second + j->first * kf.back());
  }
  cout << ans;
}

### 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;
int main() {
  ios_base::sync_with_stdio(0);
  int n;
  cin >> n;
  vector<long long> v, kf;
  for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    if (i > 0 && v.back() <= x)
      kf.back() = i + 1;
    else {
      v.push_back(x);
      kf.push_back(i + 1);
    }
  }
  n = v.size();
  set<pair<long long, long long> > st;
  st.insert(make_pair(v[0] - 1, 0));
  for (int i = 0; i < n; i++)
    if (i > 0) {
      vector<pair<long long, long long> > change;
      pair<long long, long long> ac = make_pair(-1, -1);
      while (st.size() > 0 && st.rbegin()->first >= v[i]) {
        pair<long long, long long> p = *st.rbegin();
        st.erase(p);
        long long k = p.first / v[i];
        long long d = (k - 1) * v[i] * kf[i - 1] + p.second;
        if (ac.second < d) ac = make_pair(v[i] - 1, d);
        change.push_back(
            make_pair(p.first - k * v[i], p.second + k * v[i] * kf[i - 1]));
      }
      for (int i = 0; i < change.size(); i++) st.insert(change[i]);
      st.insert(ac);
    }
  long long ans = 0;
  for (auto j = st.begin(); j != st.end(); j++) {
    ans = max(ans, j->second + j->first * kf.back());
  }
  cout << ans;
}

```