#include <bits/stdc++.h>
using namespace std;
template <typename S, typename T>
ostream& operator<<(ostream& out, pair<S, T> const& p) {
  out << '(' << p.first << ", " << p.second << ')';
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> const& v) {
  int l = v.size();
  for (int i = 0; i < l - 1; i++) out << v[i] << ' ';
  if (l > 0) out << v[l - 1];
  return out;
}
template <typename T>
void trace(const char* name, T&& arg1) {
  cout << name << " : " << arg1 << endl;
}
template <typename T, typename... Args>
void trace(const char* names, T&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  trace(comma + 1, args...);
}
const int N = 200200;
long long a[N];
long long dp[N];
int n;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  for (int i = n; i > 0; i--) cin >> a[i];
  for (int i = n - 1; i > 0; i--) a[i] = min(a[i], a[i + 1]);
  for (int i = 1; i <= n; i++) {
    long long val = a[i];
    long long sum = 0;
    while (val > 0) {
      int k = lower_bound(a + 1, a + n + 1, val) - a - 1;
      if (k > 0) {
        dp[i] = max(dp[i], dp[k] + (val - val % a[k] - a[k]) * (n - k) + sum);
        sum += (val - val % a[k]) * (n - k);
        val %= a[k];
      } else {
        dp[i] = max(dp[i], (val - 1) * n + sum);
        break;
      }
    }
  }
  cout << dp[n] << endl;
  return 0;
}

### Prompt

Please create a solution in CPP 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;
template <typename S, typename T>
ostream& operator<<(ostream& out, pair<S, T> const& p) {
  out << '(' << p.first << ", " << p.second << ')';
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> const& v) {
  int l = v.size();
  for (int i = 0; i < l - 1; i++) out << v[i] << ' ';
  if (l > 0) out << v[l - 1];
  return out;
}
template <typename T>
void trace(const char* name, T&& arg1) {
  cout << name << " : " << arg1 << endl;
}
template <typename T, typename... Args>
void trace(const char* names, T&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  trace(comma + 1, args...);
}
const int N = 200200;
long long a[N];
long long dp[N];
int n;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  for (int i = n; i > 0; i--) cin >> a[i];
  for (int i = n - 1; i > 0; i--) a[i] = min(a[i], a[i + 1]);
  for (int i = 1; i <= n; i++) {
    long long val = a[i];
    long long sum = 0;
    while (val > 0) {
      int k = lower_bound(a + 1, a + n + 1, val) - a - 1;
      if (k > 0) {
        dp[i] = max(dp[i], dp[k] + (val - val % a[k] - a[k]) * (n - k) + sum);
        sum += (val - val % a[k]) * (n - k);
        val %= a[k];
      } else {
        dp[i] = max(dp[i], (val - 1) * n + sum);
        break;
      }
    }
  }
  cout << dp[n] << endl;
  return 0;
}

```