#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &x) {
  return os << "(" << x.first << "," << x.second << ")";
}
namespace dbg_ns {
template <typename C>
struct is_iterable {
  template <class T>
  static long check(...);
  template <class T>
  static char check(int, typename T::const_iterator = C().end());
  enum {
    value = sizeof(check<C>(0)) == sizeof(char),
    neg_value = sizeof(check<C>(0)) != sizeof(char)
  };
};
template <class T>
ostream &_out_str(ostream &os, const T &x) {
  return os << '"' << x << '"';
}
template <class T>
ostream &_dbg2_5(ostream &, const T &);
template <bool B, typename T = void>
using eit = typename enable_if<B, T>::type;
template <class T>
inline ostream &_dbg3(ostream &os, eit<is_iterable<T>::neg_value, const T> &x) {
  return os << x;
}
template <class T>
inline ostream &_dbg3(ostream &os, eit<is_iterable<T>::value, const T> &V) {
  os << "{";
  bool ff = 0;
  for (const auto &E : V) _dbg2_5(ff ? os << "," : os, E), ff = 1;
  return os << "}";
}
template <>
inline ostream &_dbg3<string>(ostream &os, const string &x) {
  return _out_str(os, x);
}
template <>
inline ostream &_dbg3<const char *>(ostream &os, const char *const &x) {
  return _out_str(os, x);
}
template <class T>
inline ostream &_dbg2_5(ostream &os, const T &x) {
  return _dbg3<T>(os, x);
}
template <class T, typename... Args>
ostream &_dbg2(ostream &os, vector<string>::iterator nm, const T &x,
               Args &&...args);
inline ostream &_dbg2(ostream &os, vector<string>::iterator) { return os; }
template <typename... Args>
inline ostream &_dbg2(ostream &os, vector<string>::iterator nm, const char *x,
                      Args &&...args) {
  return _dbg2(_dbg3<const char *>(os << "  ", x), nm + 1, args...);
}
template <class T, typename... Args>
inline ostream &_dbg2(ostream &os, vector<string>::iterator nm, const T &x,
                      Args &&...args) {
  return _dbg2(_dbg3<T>(os << "  " << *nm << "=", x), nm + 1, args...);
}
vector<string> split(string s) {
  vector<string> Z;
  string z = "";
  s += ',';
  int dep = 0;
  for (char c : s) {
    if (c == ',' && !dep)
      Z.push_back(z), z = "";
    else
      z += c;
    if (c == '(') ++dep;
    if (c == ')') --dep;
  }
  return Z;
}
template <typename... Args>
inline ostream &_dbg1(int ln, const string &nm, Args &&...args) {
  auto nms = split(nm);
  return _dbg2(cerr << "L" << ln << ":", nms.begin(), args...) << endl;
}
}  // namespace dbg_ns
typedef long double ld;
const ld eps = (ld)1e-8;
const ld tau = 2 * (ld)acosl(-1);
const int inf = 1e9 + 99;
const long long linf = 1e18 + 99;
const int P = 1e9 + 7;
const int N = 200 << 10;
int n;
long long a[N];
map<long long, long long> mm;
void INS(long long a, long long f) {
  vector<pair<long long, long long> > to_ins;
  auto it = mm.lower_bound(a - 1);
  if (it != mm.end()) {
    long long z = it->second;
    for (; it != mm.end();) {
      long long ex = it->first - (a - 1);
      z = max(z, it->second + f * (ex / a) * a);
      ++it;
    }
    to_ins.push_back({a - 1, z});
  }
  for (;;) {
    it = mm.end();
    if (it == mm.begin()) break;
    --it;
    if (it->first < a) break;
    long long na = it->first % a;
    to_ins.push_back({na, it->second + f * (it->first - na)});
    mm.erase(it);
  }
  for (const auto &P : to_ins) {
    if (!mm.count(P.first) || mm[P.first] < P.second) mm[P.first] = P.second;
  }
}
int32_t main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", a + i);
  mm[a[1] - 1] = 0;
  for (int i = 2; i <= n; i++) INS(a[i], i - 1);
  long long Z = a[1] - 1;
  for (const auto &P : mm) Z = max(Z, n * P.first + P.second);
  printf("%lld\n", Z);
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &x) {
  return os << "(" << x.first << "," << x.second << ")";
}
namespace dbg_ns {
template <typename C>
struct is_iterable {
  template <class T>
  static long check(...);
  template <class T>
  static char check(int, typename T::const_iterator = C().end());
  enum {
    value = sizeof(check<C>(0)) == sizeof(char),
    neg_value = sizeof(check<C>(0)) != sizeof(char)
  };
};
template <class T>
ostream &_out_str(ostream &os, const T &x) {
  return os << '"' << x << '"';
}
template <class T>
ostream &_dbg2_5(ostream &, const T &);
template <bool B, typename T = void>
using eit = typename enable_if<B, T>::type;
template <class T>
inline ostream &_dbg3(ostream &os, eit<is_iterable<T>::neg_value, const T> &x) {
  return os << x;
}
template <class T>
inline ostream &_dbg3(ostream &os, eit<is_iterable<T>::value, const T> &V) {
  os << "{";
  bool ff = 0;
  for (const auto &E : V) _dbg2_5(ff ? os << "," : os, E), ff = 1;
  return os << "}";
}
template <>
inline ostream &_dbg3<string>(ostream &os, const string &x) {
  return _out_str(os, x);
}
template <>
inline ostream &_dbg3<const char *>(ostream &os, const char *const &x) {
  return _out_str(os, x);
}
template <class T>
inline ostream &_dbg2_5(ostream &os, const T &x) {
  return _dbg3<T>(os, x);
}
template <class T, typename... Args>
ostream &_dbg2(ostream &os, vector<string>::iterator nm, const T &x,
               Args &&...args);
inline ostream &_dbg2(ostream &os, vector<string>::iterator) { return os; }
template <typename... Args>
inline ostream &_dbg2(ostream &os, vector<string>::iterator nm, const char *x,
                      Args &&...args) {
  return _dbg2(_dbg3<const char *>(os << "  ", x), nm + 1, args...);
}
template <class T, typename... Args>
inline ostream &_dbg2(ostream &os, vector<string>::iterator nm, const T &x,
                      Args &&...args) {
  return _dbg2(_dbg3<T>(os << "  " << *nm << "=", x), nm + 1, args...);
}
vector<string> split(string s) {
  vector<string> Z;
  string z = "";
  s += ',';
  int dep = 0;
  for (char c : s) {
    if (c == ',' && !dep)
      Z.push_back(z), z = "";
    else
      z += c;
    if (c == '(') ++dep;
    if (c == ')') --dep;
  }
  return Z;
}
template <typename... Args>
inline ostream &_dbg1(int ln, const string &nm, Args &&...args) {
  auto nms = split(nm);
  return _dbg2(cerr << "L" << ln << ":", nms.begin(), args...) << endl;
}
}  // namespace dbg_ns
typedef long double ld;
const ld eps = (ld)1e-8;
const ld tau = 2 * (ld)acosl(-1);
const int inf = 1e9 + 99;
const long long linf = 1e18 + 99;
const int P = 1e9 + 7;
const int N = 200 << 10;
int n;
long long a[N];
map<long long, long long> mm;
void INS(long long a, long long f) {
  vector<pair<long long, long long> > to_ins;
  auto it = mm.lower_bound(a - 1);
  if (it != mm.end()) {
    long long z = it->second;
    for (; it != mm.end();) {
      long long ex = it->first - (a - 1);
      z = max(z, it->second + f * (ex / a) * a);
      ++it;
    }
    to_ins.push_back({a - 1, z});
  }
  for (;;) {
    it = mm.end();
    if (it == mm.begin()) break;
    --it;
    if (it->first < a) break;
    long long na = it->first % a;
    to_ins.push_back({na, it->second + f * (it->first - na)});
    mm.erase(it);
  }
  for (const auto &P : to_ins) {
    if (!mm.count(P.first) || mm[P.first] < P.second) mm[P.first] = P.second;
  }
}
int32_t main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", a + i);
  mm[a[1] - 1] = 0;
  for (int i = 2; i <= n; i++) INS(a[i], i - 1);
  long long Z = a[1] - 1;
  for (const auto &P : mm) Z = max(Z, n * P.first + P.second);
  printf("%lld\n", Z);
}

```