#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10, mod = 1e9 + 7;
const long long inf = 1e18;
long long a[maxn];
set<pair<long long, long long> > dp;
void add(long long a, long long b) {
  auto it = dp.upper_bound({a, -1});
  if (it == dp.end()) {
    dp.insert({a, b});
    return;
  }
  if ((it->second) >= b) return;
  if ((it->first) == a) dp.erase(it);
  dp.insert({a, b});
  it = dp.find({a, b});
  while (it != dp.begin() && (prev(it)->second) <= b) dp.erase(prev(it));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (i != 0 && a[i - 1] < a[i]) a[i] = a[i - 1];
  }
  a[n++] = 1;
  dp.insert({a[0] - 1, 0});
  for (int i = 1; i < n; i++) {
    long long num = 0;
    auto it = dp.rbegin();
    while ((it->first) >= a[i]) {
      long long x = (it->first) / a[i];
      num = max(num, (it->second) + (x - 1) * a[i] * i),
      add((it->first) % a[i], (it->second) + x * a[i] * i);
      dp.erase(*it), it = dp.rbegin();
    }
    add(a[i] - 1, num);
  }
  return cout << (dp.begin()->second) << endl, 0;
}

### Prompt

Please formulate 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;
const int maxn = 2e5 + 10, mod = 1e9 + 7;
const long long inf = 1e18;
long long a[maxn];
set<pair<long long, long long> > dp;
void add(long long a, long long b) {
  auto it = dp.upper_bound({a, -1});
  if (it == dp.end()) {
    dp.insert({a, b});
    return;
  }
  if ((it->second) >= b) return;
  if ((it->first) == a) dp.erase(it);
  dp.insert({a, b});
  it = dp.find({a, b});
  while (it != dp.begin() && (prev(it)->second) <= b) dp.erase(prev(it));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (i != 0 && a[i - 1] < a[i]) a[i] = a[i - 1];
  }
  a[n++] = 1;
  dp.insert({a[0] - 1, 0});
  for (int i = 1; i < n; i++) {
    long long num = 0;
    auto it = dp.rbegin();
    while ((it->first) >= a[i]) {
      long long x = (it->first) / a[i];
      num = max(num, (it->second) + (x - 1) * a[i] * i),
      add((it->first) % a[i], (it->second) + x * a[i] * i);
      dp.erase(*it), it = dp.rbegin();
    }
    add(a[i] - 1, num);
  }
  return cout << (dp.begin()->second) << endl, 0;
}

```