#include <bits/stdc++.h>
using namespace std;
namespace mine {
const int INF = 0x3f3f3f3f;
const long long LLINF = 0x3f3f3f3f3f3f3f3fll;
long long qread() {
  long long ans = 0;
  char c = getchar();
  int f = 1;
  while (c < '0' or c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c and c <= '9') ans = ans * 10 + c - '0', c = getchar();
  return ans * f;
}
void write(long long num) {
  if (num < 0) {
    num = -num;
    putchar('-');
  }
  if (num > 9) write(num / 10);
  putchar('0' + num % 10);
}
void write1(long long num) {
  write(num);
  putchar(' ');
}
void write2(long long num) {
  write(num);
  puts("");
}
void chmax(int &x, const int y) { x = x > y ? x : y; }
void chmin(int &x, const int y) { x = x < y ? x : y; }
int MOD = 1e9 + 7;
void add(int &x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  if (x <= -MOD) x += MOD;
}
long long qpower(long long x, long long e) {
  long long ans = 1;
  while (e) {
    if (e & 1) ans = ans * x % MOD;
    x = x * x % MOD;
    e >>= 1;
  }
  return ans;
}
long long inv(long long x) { return qpower(x, MOD - 2); }
const int MAX_N = 1e6 + 10;
long long a[MAX_N];
map<long long, long long> g;
void main() {
  int n = qread();
  for (int i = 1; i <= n; i++) a[i] = qread();
  g[a[1] - 1] = 0;
  for (int i = 1; i < n; i++) {
    long long lstg = -1, A = a[i + 1];
    for (map<long long, long long>::iterator it = g.lower_bound(A);
         it != g.end(); it++) {
      long long mx = it->first, gg = it->second;
      g[mx % A] = max(g[mx % A], (mx - mx % A) * i + gg);
      g[A - 1] = max(g[A - 1], ((mx + 1 - A) / A) * A * i + gg);
      if (g.count(lstg)) g.erase(g.find(lstg));
      lstg = it->first;
    }
    if (g.count(lstg)) g.erase(g.find(lstg));
  }
  long long ans = 0;
  for (map<long long, long long>::iterator it = g.begin(); it != g.end(); it++)
    ans = max(ans, it->first * n + it->second);
  write(ans);
}
};  // namespace mine
signed main() {
  srand(time(0));
  mine::main();
}

### 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;
namespace mine {
const int INF = 0x3f3f3f3f;
const long long LLINF = 0x3f3f3f3f3f3f3f3fll;
long long qread() {
  long long ans = 0;
  char c = getchar();
  int f = 1;
  while (c < '0' or c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c and c <= '9') ans = ans * 10 + c - '0', c = getchar();
  return ans * f;
}
void write(long long num) {
  if (num < 0) {
    num = -num;
    putchar('-');
  }
  if (num > 9) write(num / 10);
  putchar('0' + num % 10);
}
void write1(long long num) {
  write(num);
  putchar(' ');
}
void write2(long long num) {
  write(num);
  puts("");
}
void chmax(int &x, const int y) { x = x > y ? x : y; }
void chmin(int &x, const int y) { x = x < y ? x : y; }
int MOD = 1e9 + 7;
void add(int &x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  if (x <= -MOD) x += MOD;
}
long long qpower(long long x, long long e) {
  long long ans = 1;
  while (e) {
    if (e & 1) ans = ans * x % MOD;
    x = x * x % MOD;
    e >>= 1;
  }
  return ans;
}
long long inv(long long x) { return qpower(x, MOD - 2); }
const int MAX_N = 1e6 + 10;
long long a[MAX_N];
map<long long, long long> g;
void main() {
  int n = qread();
  for (int i = 1; i <= n; i++) a[i] = qread();
  g[a[1] - 1] = 0;
  for (int i = 1; i < n; i++) {
    long long lstg = -1, A = a[i + 1];
    for (map<long long, long long>::iterator it = g.lower_bound(A);
         it != g.end(); it++) {
      long long mx = it->first, gg = it->second;
      g[mx % A] = max(g[mx % A], (mx - mx % A) * i + gg);
      g[A - 1] = max(g[A - 1], ((mx + 1 - A) / A) * A * i + gg);
      if (g.count(lstg)) g.erase(g.find(lstg));
      lstg = it->first;
    }
    if (g.count(lstg)) g.erase(g.find(lstg));
  }
  long long ans = 0;
  for (map<long long, long long>::iterator it = g.begin(); it != g.end(); it++)
    ans = max(ans, it->first * n + it->second);
  write(ans);
}
};  // namespace mine
signed main() {
  srand(time(0));
  mine::main();
}

```