#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int o;
map<long long, long long> s;
long long n, a[N];
int ta = 0, td = 0;
pair<long long, long long> toadd[2 * N], todel[2 * N];
void update(long long j, long long v) { toadd[++ta] = make_pair(j, v); }
void vmax(long long &a, long long b) { a = max(a, b); }
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%I64d", &a[i]);
  }
  long long mx = 0;
  s[a[1] - 1] = 0;
  for (int i = 2; i <= n; i++) {
    vmax(mx, s.size());
    map<long long, long long>::iterator it = s.lower_bound(a[i]);
    for (; it != s.end(); it++) {
      long long j = (*it).first, k = (*it).second;
      if (j >= a[i]) {
        update(j % a[i], k + (i - 1) * (j - j % a[i]));
        update(a[i] - 1, k + (i - 1) * a[i] * ((j + 1) / a[i] - 1));
        todel[++td] = *it;
      }
    }
    while (td)
      if (s.count(todel[td].first))
        s.erase(todel[td--].first);
      else
        td--;
    while (ta) {
      if (s.count(toadd[ta].first)) {
        vmax(s[toadd[ta].first], toadd[ta].second);
      } else
        s[toadd[ta].first] = toadd[ta].second;
      ta--;
    }
  }
  long long ans = 0;
  for (map<long long, long long>::iterator it = s.begin(); it != s.end();
       it++) {
    ans = max(ans, n * (*it).first + (*it).second);
  }
  cout << ans << endl;
}

### Prompt

Develop a solution in cpp to the problem described below:

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 N = 5e5 + 10;
int o;
map<long long, long long> s;
long long n, a[N];
int ta = 0, td = 0;
pair<long long, long long> toadd[2 * N], todel[2 * N];
void update(long long j, long long v) { toadd[++ta] = make_pair(j, v); }
void vmax(long long &a, long long b) { a = max(a, b); }
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%I64d", &a[i]);
  }
  long long mx = 0;
  s[a[1] - 1] = 0;
  for (int i = 2; i <= n; i++) {
    vmax(mx, s.size());
    map<long long, long long>::iterator it = s.lower_bound(a[i]);
    for (; it != s.end(); it++) {
      long long j = (*it).first, k = (*it).second;
      if (j >= a[i]) {
        update(j % a[i], k + (i - 1) * (j - j % a[i]));
        update(a[i] - 1, k + (i - 1) * a[i] * ((j + 1) / a[i] - 1));
        todel[++td] = *it;
      }
    }
    while (td)
      if (s.count(todel[td].first))
        s.erase(todel[td--].first);
      else
        td--;
    while (ta) {
      if (s.count(toadd[ta].first)) {
        vmax(s[toadd[ta].first], toadd[ta].second);
      } else
        s[toadd[ta].first] = toadd[ta].second;
      ta--;
    }
  }
  long long ans = 0;
  for (map<long long, long long>::iterator it = s.begin(); it != s.end();
       it++) {
    ans = max(ans, n * (*it).first + (*it).second);
  }
  cout << ans << endl;
}

```