#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char x = '\0';
  long long fh = 1, sum = 0;
  for (x = getchar(); x < '0' || x > '9'; x = getchar())
    if (x == '-') fh = -1;
  for (; x >= '0' && x <= '9'; x = getchar()) sum = sum * 10 + x - '0';
  return fh * sum;
}
const int N = 200009;
long long n, a[N];
map<long long, long long, greater<long long> > mp;
long long tmp[N], cnt;
int main() {
  n = read();
  for (register int i = 1, endi = n; i <= endi; ++i) a[i] = read();
  mp[a[1] - 1] = 0;
  for (register int i = 1, endi = n - 1; i <= endi; ++i) {
    cnt = 0;
    for (auto x : mp) {
      long long r = x.first, k = x.second;
      if (r < a[i + 1]) break;
      mp[a[i + 1] - 1] =
          max(mp[a[i + 1] - 1], k + i * (r - r % a[i + 1] - a[i + 1]));
      mp[r % a[i + 1]] = max(mp[r % a[i + 1]], k + i * (r - r % a[i + 1]));
      tmp[++cnt] = r;
    }
    while (cnt) mp.erase(tmp[cnt]), cnt--;
  }
  long long ans = 0;
  for (auto x : mp) {
    long long r = x.first, k = x.second;
    ans = max(ans, r * n + k);
  }
  printf("%lld", ans);
  return 0;
}

### Prompt

Please provide a CPP coded solution 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;
inline long long read() {
  char x = '\0';
  long long fh = 1, sum = 0;
  for (x = getchar(); x < '0' || x > '9'; x = getchar())
    if (x == '-') fh = -1;
  for (; x >= '0' && x <= '9'; x = getchar()) sum = sum * 10 + x - '0';
  return fh * sum;
}
const int N = 200009;
long long n, a[N];
map<long long, long long, greater<long long> > mp;
long long tmp[N], cnt;
int main() {
  n = read();
  for (register int i = 1, endi = n; i <= endi; ++i) a[i] = read();
  mp[a[1] - 1] = 0;
  for (register int i = 1, endi = n - 1; i <= endi; ++i) {
    cnt = 0;
    for (auto x : mp) {
      long long r = x.first, k = x.second;
      if (r < a[i + 1]) break;
      mp[a[i + 1] - 1] =
          max(mp[a[i + 1] - 1], k + i * (r - r % a[i + 1] - a[i + 1]));
      mp[r % a[i + 1]] = max(mp[r % a[i + 1]], k + i * (r - r % a[i + 1]));
      tmp[++cnt] = r;
    }
    while (cnt) mp.erase(tmp[cnt]), cnt--;
  }
  long long ans = 0;
  for (auto x : mp) {
    long long r = x.first, k = x.second;
    ans = max(ans, r * n + k);
  }
  printf("%lld", ans);
  return 0;
}

```