#include <bits/stdc++.h>
using namespace std;
template <class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template <class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template <class T>
struct vec<T, 1> : vector<T> {
  template <class... Args>
  vec(Args... args) : vector<T>(args...) {}
};
template <class T>
inline bool Minimize(T& a, const T& b) {
  return a > b ? a = b, true : false;
}
template <class T>
inline bool Maximize(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }
mt19937 rng(static_cast<uint32_t>(
    chrono::steady_clock::now().time_since_epoch().count()));
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n_a;
  cin >> n_a;
  vec<int64_t, 1> a(n_a);
  for (auto& i : a) {
    cin >> i;
  }
  map<int64_t, int64_t> f;
  f[a[0] - 1] = 0;
  for (int i = 1; i < n_a; ++i) {
    for (; f.rbegin()->first >= a[i]; f.erase(prev(f.end()))) {
      Maximize(f[f.rbegin()->first % a[i]],
               f.rbegin()->second +
                   (f.rbegin()->first - f.rbegin()->first % a[i]) * i);
      Maximize(f[a[i] - 1],
               f.rbegin()->second +
                   (f.rbegin()->first - f.rbegin()->first % a[i] - a[i]) * i);
    }
  }
  int64_t answer = 0;
  for (auto& state : f) {
    Maximize(answer, state.first * n_a + state.second);
  }
  cout << answer << '\n';
  return 0;
}

### 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;
template <class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template <class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template <class T>
struct vec<T, 1> : vector<T> {
  template <class... Args>
  vec(Args... args) : vector<T>(args...) {}
};
template <class T>
inline bool Minimize(T& a, const T& b) {
  return a > b ? a = b, true : false;
}
template <class T>
inline bool Maximize(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }
mt19937 rng(static_cast<uint32_t>(
    chrono::steady_clock::now().time_since_epoch().count()));
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n_a;
  cin >> n_a;
  vec<int64_t, 1> a(n_a);
  for (auto& i : a) {
    cin >> i;
  }
  map<int64_t, int64_t> f;
  f[a[0] - 1] = 0;
  for (int i = 1; i < n_a; ++i) {
    for (; f.rbegin()->first >= a[i]; f.erase(prev(f.end()))) {
      Maximize(f[f.rbegin()->first % a[i]],
               f.rbegin()->second +
                   (f.rbegin()->first - f.rbegin()->first % a[i]) * i);
      Maximize(f[a[i] - 1],
               f.rbegin()->second +
                   (f.rbegin()->first - f.rbegin()->first % a[i] - a[i]) * i);
    }
  }
  int64_t answer = 0;
  for (auto& state : f) {
    Maximize(answer, state.first * n_a + state.second);
  }
  cout << answer << '\n';
  return 0;
}

```