#include <bits/stdc++.h>
using namespace std;
void upd(long long& x, long long y) { x = max(x, y); }
long long g[200005];
map<long long, long long> dp[2];
int main() {
  ios::sync_with_stdio(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> g[i];
  int now = 1;
  dp[now ^ 1][g[1] - 1] = 0;
  for (int i = 1; i < n; i++) {
    dp[now].clear();
    for (map<long long, long long>::iterator nxt,
         it = dp[now ^ 1].upper_bound(g[i + 1] - 1);
         it != dp[now ^ 1].end(); it = nxt) {
      long long r = it->first;
      long long k = it->second;
      if (r < g[i + 1])
        upd(dp[now][r], k);
      else {
        upd(dp[now][r % g[i + 1]], k + (long long)(r - r % g[i + 1]) * i);
        upd(dp[now][g[i + 1] - 1],
            k + (long long)(r - r % g[i + 1] - g[i + 1]) * i);
      }
      it++;
      nxt = it;
      it--;
      dp[now ^ 1].erase(it);
    }
    for (map<long long, long long>::iterator it = dp[now].begin();
         it != dp[now].end(); it++)
      upd(dp[now ^ 1][it->first], it->second);
  }
  long long ans = 0;
  for (map<long long, long long>::iterator it = dp[now ^ 1].begin();
       it != dp[now ^ 1].end(); it++)
    ans = max(ans, (long long)it->first * n + it->second);
  cout << ans << endl;
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
void upd(long long& x, long long y) { x = max(x, y); }
long long g[200005];
map<long long, long long> dp[2];
int main() {
  ios::sync_with_stdio(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> g[i];
  int now = 1;
  dp[now ^ 1][g[1] - 1] = 0;
  for (int i = 1; i < n; i++) {
    dp[now].clear();
    for (map<long long, long long>::iterator nxt,
         it = dp[now ^ 1].upper_bound(g[i + 1] - 1);
         it != dp[now ^ 1].end(); it = nxt) {
      long long r = it->first;
      long long k = it->second;
      if (r < g[i + 1])
        upd(dp[now][r], k);
      else {
        upd(dp[now][r % g[i + 1]], k + (long long)(r - r % g[i + 1]) * i);
        upd(dp[now][g[i + 1] - 1],
            k + (long long)(r - r % g[i + 1] - g[i + 1]) * i);
      }
      it++;
      nxt = it;
      it--;
      dp[now ^ 1].erase(it);
    }
    for (map<long long, long long>::iterator it = dp[now].begin();
         it != dp[now].end(); it++)
      upd(dp[now ^ 1][it->first], it->second);
  }
  long long ans = 0;
  for (map<long long, long long>::iterator it = dp[now ^ 1].begin();
       it != dp[now ^ 1].end(); it++)
    ans = max(ans, (long long)it->first * n + it->second);
  cout << ans << endl;
  return 0;
}

```