#include using namespace std; using ll = long long; struct Mo { const int width; vector ls, rs, ord; Mo(int n) : width((int)sqrt(n)) {} inline void insert(int l, int r) { ls.emplace_back(l); rs.emplace_back(r); } inline void build() { ord.resize(ls.size()); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](const int a, const int b) { int ablock = ls[a] / width, bblock = ls[b] / width; if (ablock != bblock) return ablock < bblock; return ablock & 1 ? rs[a] < rs[b] : rs[a] > rs[b]; }); } // void add(int idx): idx番目の要素を追加 // void del(int idx): idx番目の要素を削除 // void calc(int idx); クエリidxを処理 template inline void run(const Add& add, const Del& del, const Calc& calc) { int nl = 0, nr = 0; for (const int idx : ord) { while (nl > ls[idx]) add(--nl); while (nr < rs[idx]) add(nr++); while (nl < ls[idx]) del(nl++); while (nr > rs[idx]) del(--nr); calc(idx); } } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } Mo mo(n); vector< vector > query_id(n + 1); int query_num = 0; for (int k = 1; k <= n; k++) { int max_num = n / k; for (int i = 0; i < max_num; i++) { query_id[k].push_back(query_num); mo.insert(i * k, (i + 1) * k); query_num++; } for (int i = 0; i < max_num; i++) { query_id[k].push_back(query_num); mo.insert(n - (i + 1) * k, n - i * k); query_num++; } } mo.build(); multiset sl, sr; auto add = [&](int idx) { if (sl.empty()) { sl.insert(a[idx]); return; } if (sr.empty()) { if (*sl.begin() <= a[idx]) sr.insert(a[idx]); else { ll tmp = *sl.begin(); sl.erase(sl.begin()); sl.insert(a[idx]); sr.insert(tmp); } return; } if (*sl.rbegin() <= a[idx] && a[idx] <= *sr.begin()) { if (sl.size() > sr.size()) sr.insert(a[idx]); else sl.insert(a[idx]); } else if (a[idx] > *sr.begin()) { if (sl.size() > sr.size()) sr.insert(a[idx]); else { ll tmp = *sr.begin(); sr.erase(sr.begin()); sl.insert(tmp); sr.insert(a[idx]); } } else { if (sl.size() == sr.size()) sl.insert(a[idx]); else { ll tmp = *sl.rbegin(); sl.erase(prev(sl.end())); sl.insert(a[idx]); sr.insert(tmp); } } }; auto del = [&](int idx) { assert(!sl.empty()); if (sr.empty()) { sl.erase(sl.find(a[idx])); return; } if (sl.size() > sr.size()) { if (a[idx] <= *sl.rbegin()) { sl.erase(sl.find(a[idx])); } else { ll tmp = *sl.rbegin(); sl.erase(prev(sl.end())); sr.erase(sr.find(a[idx])); sr.insert(tmp); } } else { if (a[idx] >= *sr.begin()) { sr.erase(sr.find(a[idx])); } else { ll tmp = *sr.begin(); sr.erase(sr.begin()); sl.erase(sl.find(a[idx])); sl.insert(tmp); } } }; vector med(query_num); auto calc = [&](int idx) { med[idx] = *sl.rbegin(); }; mo.run(add, del, calc); ll ans = 0; for (int k = 1; k <= n; k++) { int max_num = n / k; vector memoL(max_num + 1, 0); ll tmp = 0; for (int i = 0; i < max_num; i++) { tmp += med[query_id[k][i]] * k; memoL[i + 1] = max(memoL[i], tmp); } vector memoR(max_num + 1, 0); tmp = 0; for (int i = 0; i < max_num; i++) { tmp += med[query_id[k][i + max_num]] * k; memoR[i + 1] = max(memoR[i], tmp); } for (int i = 0; i <= max_num; i++) { ans = max(ans, memoL[i] + memoR[max_num - i]); } } cout << ans << "\n"; return 0; }