#include <bits/stdc++.h>
using namespace std;
set<pair<int64_t, int64_t>> inc;
void add(int64_t pos, int64_t val) {
  if (pos == 0) return;
  auto p = make_pair(pos, val);
  set<pair<int64_t, int64_t>>::iterator it;
  it = inc.lower_bound(p);
  if (it != inc.end() && it->second >= val) return;
  while (true) {
    it = inc.lower_bound(p);
    if (it != inc.begin() && prev(it)->second < val)
      inc.erase(prev(it));
    else
      break;
  }
  inc.insert(p);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int64_t> A(N + 1);
  for (int i = 1; i <= N; ++i) cin >> A[i];
  inc.emplace(A[1], 0);
  for (int i = 2; i <= N; ++i) {
    int64_t cur = A[i];
    if (cur >= inc.rbegin()->first) continue;
    int64_t bestY = inc.rbegin()->second;
    while (!inc.empty() && inc.rbegin()->first > cur) {
      int64_t x, y;
      tie(x, y) = *inc.rbegin();
      inc.erase(prev(inc.end()));
      add(x % cur, y + (x / cur) * cur * (i - 1));
      bestY = max(bestY, y + (x / cur - 1) * cur * (i - 1));
    }
    add(cur, bestY);
  }
  int64_t ans = 0;
  for (auto p : inc) ans = max(ans, (p.first - 1) * N + p.second);
  cout << ans << endl;
}

### Prompt

Your task is to create 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;
set<pair<int64_t, int64_t>> inc;
void add(int64_t pos, int64_t val) {
  if (pos == 0) return;
  auto p = make_pair(pos, val);
  set<pair<int64_t, int64_t>>::iterator it;
  it = inc.lower_bound(p);
  if (it != inc.end() && it->second >= val) return;
  while (true) {
    it = inc.lower_bound(p);
    if (it != inc.begin() && prev(it)->second < val)
      inc.erase(prev(it));
    else
      break;
  }
  inc.insert(p);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int64_t> A(N + 1);
  for (int i = 1; i <= N; ++i) cin >> A[i];
  inc.emplace(A[1], 0);
  for (int i = 2; i <= N; ++i) {
    int64_t cur = A[i];
    if (cur >= inc.rbegin()->first) continue;
    int64_t bestY = inc.rbegin()->second;
    while (!inc.empty() && inc.rbegin()->first > cur) {
      int64_t x, y;
      tie(x, y) = *inc.rbegin();
      inc.erase(prev(inc.end()));
      add(x % cur, y + (x / cur) * cur * (i - 1));
      bestY = max(bestY, y + (x / cur - 1) * cur * (i - 1));
    }
    add(cur, bestY);
  }
  int64_t ans = 0;
  for (auto p : inc) ans = max(ans, (p.first - 1) * N + p.second);
  cout << ans << endl;
}

```