#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
long long a[N], b[N];
long long dp[N];
int p[N];
int n, m;
long long ans;
void calc(long long x, long long w) {
  if (x == 0) return;
  int i = upper_bound(b + 1, b + 1 + m, x) - b - 1;
  long long y;
  if (!i) {
    ans = max(ans, w + 1ll * (x - 1) * n);
    return;
  }
  y = x % b[i];
  dp[i] = max(dp[i], w + 1ll * (p[i] - 1) * (x - y - b[i]));
  calc(y, w + 1ll * (p[i] - 1) * (x - y));
}
int main() {
  int i;
  long long x;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  b[++m] = a[1];
  p[1] = 1;
  for (i = 2; i <= n; i++)
    if (a[i] < b[m]) {
      b[++m] = a[i];
      p[m] = i;
    }
  reverse(b + 1, b + 1 + m);
  reverse(p + 1, p + 1 + m);
  for (i = m; i > 1; i--) {
    x = b[i] % b[i - 1];
    dp[i - 1] =
        max(dp[i - 1], dp[i] + 1ll * (p[i - 1] - 1) * (b[i] - x - b[i - 1]));
    calc(x, dp[i] + 1ll * (p[i - 1] - 1) * (b[i] - x));
  }
  ans = max(ans, dp[1] + 1ll * (b[1] - 1) * n);
  printf("%I64d\n", ans);
}

### Prompt

Please create a solution in CPP 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;
const int N = 200010;
long long a[N], b[N];
long long dp[N];
int p[N];
int n, m;
long long ans;
void calc(long long x, long long w) {
  if (x == 0) return;
  int i = upper_bound(b + 1, b + 1 + m, x) - b - 1;
  long long y;
  if (!i) {
    ans = max(ans, w + 1ll * (x - 1) * n);
    return;
  }
  y = x % b[i];
  dp[i] = max(dp[i], w + 1ll * (p[i] - 1) * (x - y - b[i]));
  calc(y, w + 1ll * (p[i] - 1) * (x - y));
}
int main() {
  int i;
  long long x;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  b[++m] = a[1];
  p[1] = 1;
  for (i = 2; i <= n; i++)
    if (a[i] < b[m]) {
      b[++m] = a[i];
      p[m] = i;
    }
  reverse(b + 1, b + 1 + m);
  reverse(p + 1, p + 1 + m);
  for (i = m; i > 1; i--) {
    x = b[i] % b[i - 1];
    dp[i - 1] =
        max(dp[i - 1], dp[i] + 1ll * (p[i - 1] - 1) * (b[i] - x - b[i - 1]));
    calc(x, dp[i] + 1ll * (p[i - 1] - 1) * (b[i] - x));
  }
  ans = max(ans, dp[1] + 1ll * (b[1] - 1) * n);
  printf("%I64d\n", ans);
}

```