发现如果取模中途没有出现 \(0\)，则可以 \(x \gets x + 1\)。
由此设 \(f_{i, j}\) 为考虑 \([1, i]\)，最后取模得到的范围是 \([0, j]\)。
设最后的结果为 \(x\)，中间结果减去 \(x\) 和为 \(y\)，那么对答案的贡献是 \(nx + y\)。
\(f_{i - 1, j}\) 可以转移到 \(f_{i, j \bmod a_i}\) 和 \(f_{i, a_i - 1}\)，注意转移到 \(f_{i, a_i - 1}\) 时要把 \(j\) 下移到 \(\bmod a_i = a_i - 1\) 的位置再计算贡献。
因为取模至多进行 \(O(\log V)\) 次，所以时间复杂度是 \(O(n \log V \log n)\)。
code
// Problem: E. Mod Mod Mod
// Contest: Codeforces - Codeforces Round 445 (Div. 1, based on Technocup 2018 Elimination Round 3)
// URL: https://codeforces.com/problemset/problem/889/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
ll n, a[maxn];
map<ll, ll> f;
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
f[a[1] - 1] = 0;
for (int i = 2; i <= n; ++i) {
for (auto it = f.lower_bound(a[i]); it != f.end(); it = f.erase(it)) {
ll x = it->fst, y = it->scd;
f[x % a[i]] = max(f[x % a[i]], y + (x - x % a[i]) * (i - 1));
f[a[i] - 1] = max(f[a[i] - 1], y + (x - (a[i] - 1)) / a[i] * a[i] * (i - 1));
}
}
ll ans = 0;
for (auto p : f) {
ans = max(ans, n * p.fst + p.scd);
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}