#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int P = 1e9 + 7;
const int inf = 1e9;
const long long Inf = 1e15;
inline int IN() {
  char ch = getchar();
  int x = 0, f = 0;
  while (ch < '0' || ch > '9') ch = getchar(), f = (ch == '-');
  while (ch >= '0' && ch <= '9') {
    x = (x << 1) + (x << 3) + ch - 48;
    ch = getchar();
  }
  return f ? (-x) : x;
}
inline int Pow(int x, int y, int p) {
  int an = 1;
  for (; y; y >>= 1, x = (long long)x * x % p)
    if (y & 1) an = (long long)an * x % p;
  return an;
}
void renew(int &x, int y) {
  x += y;
  if (x < 0)
    x += P;
  else if (x >= P)
    x -= P;
}
void setIO(string a) {
  freopen((a + ".in").c_str(), "r", stdin);
  freopen((a + ".out").c_str(), "w", stdout);
}
template <typename T>
inline void chkmin(T &a, const T &b) {
  if (a > b) a = b;
}
template <typename T>
inline void chkmax(T &a, const T &b) {
  if (a < b) a = b;
}
int n;
long long a[N];
inline int cmp(const long long &a, const long long &b) { return a > b; }
map<pair<int, long long>, long long> mps;
long long dp(int x, long long v) {
  if (x >= n) return v * n;
  if (v == 0) return 0;
  if (mps.count(make_pair(x, v))) return mps[make_pair(x, v)];
  x++;
  if (v >= a[x]) {
    long long now = v % a[x];
    long long &res = mps[make_pair(x - 1, v)];
    res = 0;
    res = max(res, dp(x, now) + (v - now) * (x - 1));
    res = max(res, dp(x, a[x] - 1) + (v - now - a[x]) * (x - 1));
    return res;
  } else {
    int nxt = lower_bound(a + x, a + n + 1, v, cmp) - a;
    if (nxt > n) return v * n;
    long long now = v % a[nxt];
    long long &res = mps[make_pair(x - 1, v)];
    res = 0;
    res = max(res, dp(nxt, now) + (v - now) * (nxt - 1));
    res = max(res, dp(nxt, a[nxt] - 1) + (v - now - a[nxt]) * (nxt - 1));
    return res;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = (int)1; i <= (int)n; i++) scanf("%lld", a + i);
  for (int i = (int)2; i <= (int)n; i++) a[i] = min(a[i], a[i - 1]);
  printf("%lld\n", dp(1, a[1] - 1));
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 = 200005;
const int P = 1e9 + 7;
const int inf = 1e9;
const long long Inf = 1e15;
inline int IN() {
  char ch = getchar();
  int x = 0, f = 0;
  while (ch < '0' || ch > '9') ch = getchar(), f = (ch == '-');
  while (ch >= '0' && ch <= '9') {
    x = (x << 1) + (x << 3) + ch - 48;
    ch = getchar();
  }
  return f ? (-x) : x;
}
inline int Pow(int x, int y, int p) {
  int an = 1;
  for (; y; y >>= 1, x = (long long)x * x % p)
    if (y & 1) an = (long long)an * x % p;
  return an;
}
void renew(int &x, int y) {
  x += y;
  if (x < 0)
    x += P;
  else if (x >= P)
    x -= P;
}
void setIO(string a) {
  freopen((a + ".in").c_str(), "r", stdin);
  freopen((a + ".out").c_str(), "w", stdout);
}
template <typename T>
inline void chkmin(T &a, const T &b) {
  if (a > b) a = b;
}
template <typename T>
inline void chkmax(T &a, const T &b) {
  if (a < b) a = b;
}
int n;
long long a[N];
inline int cmp(const long long &a, const long long &b) { return a > b; }
map<pair<int, long long>, long long> mps;
long long dp(int x, long long v) {
  if (x >= n) return v * n;
  if (v == 0) return 0;
  if (mps.count(make_pair(x, v))) return mps[make_pair(x, v)];
  x++;
  if (v >= a[x]) {
    long long now = v % a[x];
    long long &res = mps[make_pair(x - 1, v)];
    res = 0;
    res = max(res, dp(x, now) + (v - now) * (x - 1));
    res = max(res, dp(x, a[x] - 1) + (v - now - a[x]) * (x - 1));
    return res;
  } else {
    int nxt = lower_bound(a + x, a + n + 1, v, cmp) - a;
    if (nxt > n) return v * n;
    long long now = v % a[nxt];
    long long &res = mps[make_pair(x - 1, v)];
    res = 0;
    res = max(res, dp(nxt, now) + (v - now) * (nxt - 1));
    res = max(res, dp(nxt, a[nxt] - 1) + (v - now - a[nxt]) * (nxt - 1));
    return res;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = (int)1; i <= (int)n; i++) scanf("%lld", a + i);
  for (int i = (int)2; i <= (int)n; i++) a[i] = min(a[i], a[i - 1]);
  printf("%lld\n", dp(1, a[1] - 1));
  return 0;
}

```