#include <bits/stdc++.h> //Logm
using namespace std;
#define int long long
const int N = 1e5+5;
int n, a[N];
vector<int> val;
int comp[N];
int bit[N];
void update(int i, int val) { // dp[i] = val
for (; i < N; i += i & -i)
bit[i] = max(bit[i], val);
}
int getmax(int i) { // lấy max(dp[1..i])
int res = 0;
for (; i > 0; i -= i & -i)
res = max(res, bit[i]);
return res;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen("_ab.inp", "r")) {
freopen("_ab.inp", "r", stdin);
freopen("_ab.out", "w", stdout);
}
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
val.push_back(a[i]);
}
// sắp xếp tất cả giá trị và loại bỏ đi những giá trị trùng lặp
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
// {2, 10, 4, 5, 2, 4, 4} -> {2, 4, 5, 10}
// lưu ý vì ctdl bit không thể update hay get ở vị trí 0
// nên cần +2 giá trị nén để không bị tràn
for (int i = 1; i <= n; ++i)
comp[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 2;
// a = {2, 10, 4, 5, 2, 4, 4}
// comp = {2, 5, 3, 4, 2, 3, 3}
int ans = 0;
for (int i = 1; i <= n; ++i) {
int last = getmax(comp[i] - 1); // tìm dp[x] lớn nhất với x < a[i]
// vì ở đây lấy max có vị trí comp[i] - 1 nên comp[i] phải > 1
update(comp[i], last + a[i]); // thêm a[i] vào dp[x] lớn nhất và cập nhật cho dp[a[i]]
ans = max(ans, last + a[i]); // lấy max kết quả
}
cout << ans;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvL0xvZ20KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBpbnQgbG9uZyBsb25nCgpjb25zdCBpbnQgTiA9IDFlNSs1OwppbnQgbiwgYVtOXTsKCnZlY3RvcjxpbnQ+IHZhbDsKaW50IGNvbXBbTl07CgppbnQgYml0W05dOwp2b2lkIHVwZGF0ZShpbnQgaSwgaW50IHZhbCkgeyAvLyBkcFtpXSA9IHZhbAogICAgZm9yICg7IGkgPCBOOyBpICs9IGkgJiAtaSkKICAgICAgICBiaXRbaV0gPSBtYXgoYml0W2ldLCB2YWwpOwp9CmludCBnZXRtYXgoaW50IGkpIHsgLy8gbOG6pXkgbWF4KGRwWzEuLmldKQogICAgaW50IHJlcyA9IDA7CiAgICBmb3IgKDsgaSA+IDA7IGkgLT0gaSAmIC1pKQogICAgICAgIHJlcyA9IG1heChyZXMsIGJpdFtpXSk7CiAgICByZXR1cm4gcmVzOwp9CgpzaWduZWQgbWFpbigpIHsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwogICAgaWYgKGZvcGVuKCJfYWIuaW5wIiwgInIiKSkgewogICAgICAgIGZyZW9wZW4oIl9hYi5pbnAiLCAiciIsIHN0ZGluKTsKICAgICAgICBmcmVvcGVuKCJfYWIub3V0IiwgInciLCBzdGRvdXQpOwogICAgfQoKICAgIGNpbiA+PiBuOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSB7CiAgICAgICAgY2luID4+IGFbaV07CiAgICAgICAgdmFsLnB1c2hfYmFjayhhW2ldKTsKICAgIH0KICAgIC8vIHPhuq9wIHjhur9wIHThuqV0IGPhuqMgZ2nDoSB0cuG7iyB2w6AgbG/huqFpIGLhu48gxJFpIG5o4buvbmcgZ2nDoSB0cuG7iyB0csO5bmcgbOG6t3AKICAgIHNvcnQodmFsLmJlZ2luKCksIHZhbC5lbmQoKSk7CiAgICB2YWwuZXJhc2UodW5pcXVlKHZhbC5iZWdpbigpLCB2YWwuZW5kKCkpLCB2YWwuZW5kKCkpOwogICAgLy8gezIsIDEwLCA0LCA1LCAyLCA0LCA0fSAtPiB7MiwgNCwgNSwgMTB9CgogICAgLy8gbMawdSDDvSB2w6wgY3RkbCBiaXQga2jDtG5nIHRo4buDIHVwZGF0ZSBoYXkgZ2V0IOG7nyB24buLIHRyw60gMAogICAgLy8gbsOqbiBj4bqnbiArMiBnacOhIHRy4buLIG7DqW4gxJHhu4Mga2jDtG5nIGLhu4sgdHLDoG4KICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47ICsraSkKICAgICAgICBjb21wW2ldID0gbG93ZXJfYm91bmQodmFsLmJlZ2luKCksIHZhbC5lbmQoKSwgYVtpXSkgLSB2YWwuYmVnaW4oKSArIDI7CiAgICAvLyBhID0gezIsIDEwLCA0LCA1LCAyLCA0LCA0fQogICAgLy8gY29tcCA9IHsyLCA1LCAzLCA0LCAyLCAzLCAzfQoKICAgIGludCBhbnMgPSAwOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSB7CiAgICAgICAgaW50IGxhc3QgPSBnZXRtYXgoY29tcFtpXSAtIDEpOyAvLyB0w6xtIGRwW3hdIGzhu5tuIG5o4bqldCB24bubaSB4IDwgYVtpXQogICAgICAgIC8vIHbDrCDhu58gxJHDonkgbOG6pXkgbWF4IGPDsyB24buLIHRyw60gY29tcFtpXSAtIDEgbsOqbiBjb21wW2ldIHBo4bqjaSA+IDEKICAgICAgICB1cGRhdGUoY29tcFtpXSwgbGFzdCArIGFbaV0pOyAvLyB0aMOqbSBhW2ldIHbDoG8gZHBbeF0gbOG7m24gbmjhuqV0IHbDoCBj4bqtcCBuaOG6rXQgY2hvIGRwW2FbaV1dCiAgICAgICAgYW5zID0gbWF4KGFucywgbGFzdCArIGFbaV0pOyAvLyBs4bqleSBtYXgga+G6v3QgcXXhuqMKICAgIH0KICAgIGNvdXQgPDwgYW5zOwogICAgcmV0dXJuIDA7Cn0K