#include <bits/stdc++.h>
using namespace std;
long long findIndex(long long L, long long R, long long val,
                    vector<long long> &v) {
  long long res = R, mid;
  while (L <= R) {
    mid = (L + R) / 2;
    if (v[mid] <= val) {
      R = mid - 1;
      res = min(res, mid);
    } else {
      L = mid + 1;
    }
  }
  return res;
}
bool work() {
  vector<long long> f;
  vector<long long> v;
  vector<long long> vIndex;
  long long N;
  if (scanf("%I64d", &N) != 1) return false;
  f.resize(N + 10);
  v.push_back(1e15);
  vIndex.push_back(0);
  for (int i = 1; i <= N; i++) {
    long long tmp;
    scanf("%I64d", &tmp);
    if (tmp < v[v.size() - 1]) {
      v.push_back(tmp);
      vIndex.push_back(i);
    }
  }
  if (v[v.size() - 1] != 1) {
    v.push_back(1);
    vIndex.push_back(N + 1);
  }
  N = v.size() - 1;
  for (int i = 0; i <= N; i++) f[i] = 0;
  f[1] = 0;
  long long res = 0;
  for (int i = 1; i < N; i++) {
    long long j = i, range = v[i] - 1, val = f[i];
    while (range != 0) {
      long long k = findIndex(j + 1, N, range, v);
      long long tmp = (range - v[k] - (range % v[k])) * (vIndex[k] - 1) + val;
      f[k] = max(f[k], tmp);
      tmp = (range - (range % v[k])) * (vIndex[k] - 1) + val;
      j = k;
      range = range % v[k];
      val = tmp;
    }
    res = max(res, val);
  }
  for (int i = N; i <= N; i++) {
    res = max(res, f[N]);
  }
  printf("%I64d\n", res);
  return true;
}
int main() {
  while (work())
    ;
  return 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;
long long findIndex(long long L, long long R, long long val,
                    vector<long long> &v) {
  long long res = R, mid;
  while (L <= R) {
    mid = (L + R) / 2;
    if (v[mid] <= val) {
      R = mid - 1;
      res = min(res, mid);
    } else {
      L = mid + 1;
    }
  }
  return res;
}
bool work() {
  vector<long long> f;
  vector<long long> v;
  vector<long long> vIndex;
  long long N;
  if (scanf("%I64d", &N) != 1) return false;
  f.resize(N + 10);
  v.push_back(1e15);
  vIndex.push_back(0);
  for (int i = 1; i <= N; i++) {
    long long tmp;
    scanf("%I64d", &tmp);
    if (tmp < v[v.size() - 1]) {
      v.push_back(tmp);
      vIndex.push_back(i);
    }
  }
  if (v[v.size() - 1] != 1) {
    v.push_back(1);
    vIndex.push_back(N + 1);
  }
  N = v.size() - 1;
  for (int i = 0; i <= N; i++) f[i] = 0;
  f[1] = 0;
  long long res = 0;
  for (int i = 1; i < N; i++) {
    long long j = i, range = v[i] - 1, val = f[i];
    while (range != 0) {
      long long k = findIndex(j + 1, N, range, v);
      long long tmp = (range - v[k] - (range % v[k])) * (vIndex[k] - 1) + val;
      f[k] = max(f[k], tmp);
      tmp = (range - (range % v[k])) * (vIndex[k] - 1) + val;
      j = k;
      range = range % v[k];
      val = tmp;
    }
    res = max(res, val);
  }
  for (int i = N; i <= N; i++) {
    res = max(res, f[N]);
  }
  printf("%I64d\n", res);
  return true;
}
int main() {
  while (work())
    ;
  return 0;
}

```