记录编号	595662	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	MATHS	最终得分	100
用户昵称	darkMoon	是否通过	通过
代码语言	C++	运行时间	2.153 s
提交时间	2024-10-15 20:15:34	内存使用	28.14 MiB

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
auto mread = [](){int x;scanf("%lld", &x);return x;};
int t = 1;
signed main(){
    while(t --){
        int n = mread();
        int a[n + 5], b[n + 5], l[n + 5], r[n + 5], e[n + 5] = {0};
        int st0[n + 5][25] = {0}, st1[n + 5][25] = {0};
        pair<int, int> p[n + 5];
        for(int i = 1; i <= n; i ++){
            cin >> a[i];
            p[i] = mp(a[i], i);
            if(i & 1){
                st1[i][0] = a[i];
            }
            else{
                st0[i][0] = a[i];
            }
        }
        sort(p + 1, p + 1 + n);
        multiset<int> se;
        int sum = 0;
        for(int j = 1; j <= 20; j ++){
            for(int i = 1; i <= n - (1 << j) + 1; i ++){
                st0[i][j] = max(st0[i][j - 1], st0[i + (1 << j - 1)][j - 1]);
                st1[i][j] = max(st1[i][j - 1], st1[i + (1 << j - 1)][j - 1]);
            }
        }
        auto makeMax0 = [&](int l, int r){
            int lg = __lg(r - l + 1);
            return max(st0[l][lg], st0[r - (1 << lg) + 1][lg]);
        };
        auto makeMax1 = [&](int l, int r){
            int lg = __lg(r - l + 1);
            return max(st1[l][lg], st1[r - (1 << lg) + 1][lg]);
        };
        auto find = [&](int l, int r, int form){
            if(form == 0){
                sum -= (r - l + 1) + 1 >> 1;
            }
            else{
                sum += (r - l + 1) + 1 >> 1;
            }
            if((r - l + 1) & 1){
                if(l & 1){
                    return max(makeMax0(l, r) - 1, makeMax1(l, r));
                }
                else{
                    return max(makeMax0(l, r), makeMax1(l, r) - 1);
                }
            }
            else{
                return max(makeMax0(l, r), makeMax1(l, r));
            }
        };
        auto add = [&](int x){
            e[x] = 1;
            l[x] = r[x] = x;
            int nl = x, nr = x;
            if(e[x - 1] == 1){
                se.erase(se.find(find(l[x - 1], r[x - 1], 0)));
                nl = l[x - 1];
                l[x] = l[x - 1];
                r[l[x - 1]] = r[x];
            }
            if(e[x + 1] == 1){
                se.erase(se.find(find(l[x + 1], r[x + 1], 0)));
                nr = r[x + 1];
                r[l[x]] = r[x + 1];
                l[r[x + 1]] = l[x];
            }
            // printf("--- %lld %lld %lld\n", x, nl, nr);
            assert(l[nl] == nl && r[nl] == nr && r[nr] == nr && l[nr] == nl);
            se.insert(find(nl, nr, 1));
            return;
        };
        int ans = 0;
        for(int i = n; i >= 1; i --){
            add(p[i].se);
            ans = max(ans, sum + max(0ll, *se.rbegin()) + p[i].fi);
            // printf("*** %lld %lld %lld %lld %lld\n", p[i].se, sum, se.size(), *se.rbegin(), sum + max(0ll, *se.begin()) + p[i].fi);
        }
        printf("%lld\n", ans);
    }
    return 0;
}