#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
const long long ooo = 9223372036854775807ll;
const int _cnt = 1000 * 1000 + 7;
const int _p = 1000 * 1000 * 1000 + 7;
const int N = 200105;
const double PI = acos(-1.0);
const double eps = 1e-9;
int o(int x) { return x % _p; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
void file_put() {
  freopen("filename.in", "r", stdin);
  freopen("filename.out", "w", stdout);
}
map<long long, long long> M;
map<long long, long long>::iterator it, iit;
vector<int> V;
vector<pair<long long, long long> > VV;
int n;
long long x, y, ans = 0;
int main() {
  scanf("%d", &n);
  M[100000000000000] = 0;
  for (int i = (1); i <= (n); ++i) {
    scanf("%I64d", &x);
    iit = it = M.lower_bound(x);
    y = 0;
    bool tt = (it != M.end());
    while (iit != M.end())
      y = max(y, iit->second + (iit->first - (x - 1)) / x * x * (i - 1)), ++iit;
    VV.clear();
    for (iit = it; iit != M.end(); iit++)
      VV.push_back(
          make_pair(iit->first % x,
                    iit->second + (iit->first - iit->first % x) * (i - 1)));
    M.erase(it, M.end());
    for (__typeof((VV).begin()) it = (VV).begin(); it != (VV).end(); it++)
      M[it->first] = max(M[it->first], it->second);
    if (tt) M[x - 1] = max(M[x - 1], y);
  }
  for (__typeof((M).begin()) it = (M).begin(); it != (M).end(); it++)
    ans = max(ans, it->second + it->first * n);
  printf("%I64d\n", ans);
  return 0;
}

### Prompt

Create a solution in cpp for 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 oo = 0x3f3f3f3f;
const long long ooo = 9223372036854775807ll;
const int _cnt = 1000 * 1000 + 7;
const int _p = 1000 * 1000 * 1000 + 7;
const int N = 200105;
const double PI = acos(-1.0);
const double eps = 1e-9;
int o(int x) { return x % _p; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
void file_put() {
  freopen("filename.in", "r", stdin);
  freopen("filename.out", "w", stdout);
}
map<long long, long long> M;
map<long long, long long>::iterator it, iit;
vector<int> V;
vector<pair<long long, long long> > VV;
int n;
long long x, y, ans = 0;
int main() {
  scanf("%d", &n);
  M[100000000000000] = 0;
  for (int i = (1); i <= (n); ++i) {
    scanf("%I64d", &x);
    iit = it = M.lower_bound(x);
    y = 0;
    bool tt = (it != M.end());
    while (iit != M.end())
      y = max(y, iit->second + (iit->first - (x - 1)) / x * x * (i - 1)), ++iit;
    VV.clear();
    for (iit = it; iit != M.end(); iit++)
      VV.push_back(
          make_pair(iit->first % x,
                    iit->second + (iit->first - iit->first % x) * (i - 1)));
    M.erase(it, M.end());
    for (__typeof((VV).begin()) it = (VV).begin(); it != (VV).end(); it++)
      M[it->first] = max(M[it->first], it->second);
    if (tt) M[x - 1] = max(M[x - 1], y);
  }
  for (__typeof((M).begin()) it = (M).begin(); it != (M).end(); it++)
    ans = max(ans, it->second + it->first * n);
  printf("%I64d\n", ans);
  return 0;
}

```