#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
template <typename T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
const int N = 200005;
map<long long, long long> dp;
long long a[N], n;
int main() {
  scanf("%lld", &n);
  for (register int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  dp[a[1] - 1] = 0;
  for (register int i = 2; i <= n; i++) {
    map<long long, long long>::iterator it = dp.lower_bound(a[i]);
    for (; it != dp.end(); dp.erase(it++)) {
      long long x = it->first, y = it->second;
      ckmax(dp[x % a[i]], y + 1ll * (i - 1) * (x - x % a[i]));
      ckmax(dp[a[i] - 1], y + 1ll * (i - 1) * ((x + 1) / a[i] - 1) * a[i]);
    }
  }
  long long ans = 0;
  map<long long, long long>::iterator it = dp.begin();
  for (; it != dp.end(); it++) {
    ckmax(ans, it->first * n + it->second);
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

In Cpp, your task is to solve 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>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
template <typename T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
const int N = 200005;
map<long long, long long> dp;
long long a[N], n;
int main() {
  scanf("%lld", &n);
  for (register int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  dp[a[1] - 1] = 0;
  for (register int i = 2; i <= n; i++) {
    map<long long, long long>::iterator it = dp.lower_bound(a[i]);
    for (; it != dp.end(); dp.erase(it++)) {
      long long x = it->first, y = it->second;
      ckmax(dp[x % a[i]], y + 1ll * (i - 1) * (x - x % a[i]));
      ckmax(dp[a[i] - 1], y + 1ll * (i - 1) * ((x + 1) / a[i] - 1) * a[i]);
    }
  }
  long long ans = 0;
  map<long long, long long>::iterator it = dp.begin();
  for (; it != dp.end(); it++) {
    ckmax(ans, it->first * n + it->second);
  }
  printf("%lld\n", ans);
  return 0;
}

```