贪心

首先如果能够确定被选择的数的上界和下界，需要做的事情就是最大化被选的数的数量。

根据样例猜测 $\max\limits_{i=1}^{n} a_i$ 一定被选，考虑一下原因。假设当前选择方案中没有选择任何等于这个值的元素 $a_j$。

• 如果存在旁边的两个数都未被选择的 $a_j$，选择 $a_j$ 显然更优。
• 如果存在旁边的两个数中有一个被选的 $a_j$，取消选择被选的那个数再选择 $a_j$ 显然更优。
• 如果 $a_{j-1}$ 和 $a_{j+1}$ 都被选，取消选择这两个数再选择 $a_j$ 会将被选择的数最大值增加至少 $1$，因此答案至少增加 $1$。取消这两个元素只会让答案减少 $1$，同时还留出了更多可选择的位置，所以选择 $a_j$ 更优。

枚举被选择的数的下界，这些被选择的数形成若干个极长连续区间。在不强制选择全局最大值的情况下每个区间可以贪心地尽量多选。

考虑在哪个区间选全局最大值。

• 存在长度为偶数且包含了至少一个全局最大值的区间时，由于这个区间的两种贪心选择方案对答案的贡献相同，所有区间都可以贪心选。
• 存在长度为奇数且包含了在区间内位于奇数位置的全局最大值的区间时，由于这个区间的贪心选择方案包含了全局最大值，所有区间都可以贪心选。
• 否则肯定区间长度全为奇数而且有一个区间需要亏 $1$ 个位置来选择最大值，这时候答案就是全部贪心选的答案再减 $1$。

用 set 维护不相交线段集合，时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
struct Segment{int l,r,o,e;Segment(int x,int y,int _o,int _e):l(x),r(y),o(_o),e(_e){}};
bool cmp(const Segment &x,const Segment &y){return x.l>y.r;}
set<Segment,decltype(&cmp)> s(cmp);
int n,ans,cnt,uim,good;
void add(int x,int i){
    Segment now(i,i,(x==uim&&(i&1)),(x==uim&&!(i&1)));
    auto it=s.find(Segment(i-1,i-1,0,0));
    if(it!=s.end()){
        now.l=it->l,now.o|=it->o,now.e|=it->e;
        if((it->r-it->l+1)&1){
            if(it->l&1) good-=it->o;
            else good-=it->e;
        }
        else good-=it->o|it->e;
        cnt-=(it->r-it->l+2)/2;
        s.erase(it);
    }
    it=s.find(Segment(i+1,i+1,0,0));
    if(it!=s.end()){
        now.r=it->r,now.o|=it->o,now.e|=it->e;
        if((it->r-it->l+1)&1){
            if(it->l&1) good-=it->o;
            else good-=it->e;
        }
        else good-=it->o|it->e;
        cnt-=(it->r-it->l+2)/2;
        s.erase(it);
    }
    if((now.r-now.l+1)&1){
        if(now.l&1) good+=now.o;
        else good+=now.e;
    }
    else good+=now.o|now.e;
    cnt+=(now.r-now.l+2)/2;
    s.emplace(now);
}
void solution(){
    cin>>n,ans=0,cnt=0,good=0,s.clear();
    vector<pair<int,int>> v(n);
    for(auto &[x,i]:v) cin>>x,i=++cnt;
    sort(v.begin(),v.end(),greater<pair<int,int>>());
    cnt=0,uim=v.front().first;
    for(auto &[x,i]:v){
        add(x,i);
        if(good!=0) ans=max(ans,uim+x+cnt);
        else ans=max(ans,uim+x+cnt-1);
    }
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}