#include <bits/stdc++.h>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
using namespace std;
inline void MAX(long long &a, long long b) {
  if (a < b) a = b;
}
long long n;
map<long long, long long> mp;
signed main() {
  read(n);
  long long x;
  read(x);
  mp[x - 1] = 0;
  for (long long i = 1; i < n; ++i) {
    long long a;
    read(a);
    for (map<long long, long long>::iterator it = --mp.end(); (*it).first >= a;
         mp.erase(it), it = --mp.end()) {
      long long j = (*it).first, v = (*it).second;
      mp[j % a] = max(mp[j % a], v + (j - j % a) * i);
      long long t = j - (j % a) - 1;
      if (t >= 0) mp[t % a] = max(mp[t % a], v + (t - t % a) * i);
    }
  }
  long long res = 0;
  for (map<long long, long long>::iterator it = mp.begin(); it != mp.end();
       ++it) {
    long long j = (*it).first, v = (*it).second;
    MAX(res, j * n + v);
  }
  printf("%lld\n", res);
  return 0;
}

### 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>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
using namespace std;
inline void MAX(long long &a, long long b) {
  if (a < b) a = b;
}
long long n;
map<long long, long long> mp;
signed main() {
  read(n);
  long long x;
  read(x);
  mp[x - 1] = 0;
  for (long long i = 1; i < n; ++i) {
    long long a;
    read(a);
    for (map<long long, long long>::iterator it = --mp.end(); (*it).first >= a;
         mp.erase(it), it = --mp.end()) {
      long long j = (*it).first, v = (*it).second;
      mp[j % a] = max(mp[j % a], v + (j - j % a) * i);
      long long t = j - (j % a) - 1;
      if (t >= 0) mp[t % a] = max(mp[t % a], v + (t - t % a) * i);
    }
  }
  long long res = 0;
  for (map<long long, long long>::iterator it = mp.begin(); it != mp.end();
       ++it) {
    long long j = (*it).first, v = (*it).second;
    MAX(res, j * n + v);
  }
  printf("%lld\n", res);
  return 0;
}

```