#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
template <typename T>
bool cmax(T &a, T b) {
  return (a < b) ? a = b, 1 : 0;
}
template <typename T>
bool cmin(T &a, T b) {
  return (a > b) ? a = b, 1 : 0;
}
template <typename T>
T read() {
  T ans = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != '-') ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (isdigit(ch))
    ans = (ans << 3) + (ans << 1) + (ch - '0'), ch = getchar();
  return ans * f;
}
template <typename T>
void write(T x, char y) {
  if (x == 0) {
    putchar('0'), putchar(y);
    return;
  }
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  static char wr[20];
  int top = 0;
  for (; x; x /= 10) wr[++top] = x % 10 + '0';
  while (top) putchar(wr[top--]);
  putchar(y);
}
void file() {}
int n;
long long a[N];
void input() {
  n = read<int>();
  for (register int i = (int)(1); i <= (int)(n); ++i) a[i] = read<long long>();
}
map<long long, long long> mp;
void work() {
  mp[a[1] - 1] = 0;
  for (register int i = (int)(2); i <= (int)(n); ++i) {
    for (auto it = mp.lower_bound(a[i]); it != mp.end();) {
      cmax(mp[it->first % a[i]],
           it->second + (it->first) / a[i] * a[i] * (i - 1));
      cmax(mp[a[i] - 1],
           it->second + ((it->first + 1) / a[i] - 1) * a[i] * (i - 1));
      auto now = it;
      ++it;
      mp.erase(now);
    }
  }
  long long ans = 0;
  for (auto it : mp) cmax(ans, it.second + it.first * n);
  write(ans, '\n');
}
int main() {
  file();
  input();
  work();
  return 0;
}

### Prompt

Your challenge is to write 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;
const int N = 2e5 + 5;
template <typename T>
bool cmax(T &a, T b) {
  return (a < b) ? a = b, 1 : 0;
}
template <typename T>
bool cmin(T &a, T b) {
  return (a > b) ? a = b, 1 : 0;
}
template <typename T>
T read() {
  T ans = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != '-') ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (isdigit(ch))
    ans = (ans << 3) + (ans << 1) + (ch - '0'), ch = getchar();
  return ans * f;
}
template <typename T>
void write(T x, char y) {
  if (x == 0) {
    putchar('0'), putchar(y);
    return;
  }
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  static char wr[20];
  int top = 0;
  for (; x; x /= 10) wr[++top] = x % 10 + '0';
  while (top) putchar(wr[top--]);
  putchar(y);
}
void file() {}
int n;
long long a[N];
void input() {
  n = read<int>();
  for (register int i = (int)(1); i <= (int)(n); ++i) a[i] = read<long long>();
}
map<long long, long long> mp;
void work() {
  mp[a[1] - 1] = 0;
  for (register int i = (int)(2); i <= (int)(n); ++i) {
    for (auto it = mp.lower_bound(a[i]); it != mp.end();) {
      cmax(mp[it->first % a[i]],
           it->second + (it->first) / a[i] * a[i] * (i - 1));
      cmax(mp[a[i] - 1],
           it->second + ((it->first + 1) / a[i] - 1) * a[i] * (i - 1));
      auto now = it;
      ++it;
      mp.erase(now);
    }
  }
  long long ans = 0;
  for (auto it : mp) cmax(ans, it.second + it.first * n);
  write(ans, '\n');
}
int main() {
  file();
  input();
  work();
  return 0;
}

```