description
给定一个长度为 \(n\) 的数组 \(a\)，要求选一些数，满足相邻的数不能都选。问最后 \(max+min+cnt\) 的最大值。其中 \(max\) 是选的数的最大值，\(min\) 是选的树的最小值，\(cnt\) 是选的数的个数。
solution
好题。
显然肯定选到一个最大值，这一点因为如果还没有加入最大值那么加入一定不会变劣。于是我们就可以去掉 \(max\) 这一项。于是枚举 \(min\)，每次加入一个数进行决策。
此时需要计算的就是 \(cnt\) 的最大值，假设现在加入的数是一些连续的段，每一段是独立的，因此我们分别计算最优的答案，接着相加即可。
对于一个连续段，肯定是选择 \(\lceil\frac{sz}{2}\rceil\) 个数。如果没有选到最大值的话那么，我们强制塞进去然后调整其它的即可。
code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<utility>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<random>
using namespace std;
#define int long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define debug(x) cout<<#x<<'='<<x<<'\n'
#define pb push_back
#define ll long long
#define x0 __x00
#define y0 __y00
#define ull unsigned long long
#define db double
#define ldb long double
#define int128 __int128
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define Base 10
template<typename tp> inline void tomax(tp &a,tp b){a=(b>a?b:a);}
template<typename tp> inline void tomin(tp &a,tp b){a=(b<a?b:a);}
template<typename tp> inline void read(tp& n){tp x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}n=x*f;}
template<typename tp> inline void print(tp x){if (x<0)putchar('-'),x=-x;if (x>9)print(x/10);putchar(x%10+'0');}
template<typename tp> inline tp qmi(tp a,tp b,tp p){tp res=1;while(b){if(b&1)res=1ll*res*a%p;b>>=1;a=1ll*a*a%p;}return res;}
pll exgcd(ll a,ll b){if(!b)return {1,0};pll tmp=exgcd(b,a%b);return {tmp.se,tmp.fi-(a/b)*tmp.se};}
template<typename tp> inline tp gcd(tp a,tp b){return !b?a:gcd(b,a%b);}
typedef class BigInteger:public vector<ll>{public: using vector<ll>:: vector;void shrink(){while(size()>1u&&!back())pop_back();}friend BigInteger operator+(BigInteger a,BigInteger b){int n=max(a.size(),b.size())+1;a.resize(n,0);b.resize(n,0);rep(j,0,n-1)if((a[j]+=b[j])>=Base){a[j]-=Base;a[j+1]+=1;}a.shrink();return a;}friend BigInteger operator/(BigInteger a,int b){int n=a.size(),p=0;per(j,n-1,0){p=p*Base+a[j];a[j]=p/b;p%=b;}a.shrink();return a;}friend BigInteger operator*(BigInteger a,BigInteger b){int n=a.size(),m=b.size();BigInteger c(n+m,0);rep(i,0,n-1)for(int j=0,s=i;j<m;j++,s++){c[s]+=a[i]*b[j];c[s+1]+=c[s]/Base;c[s]%=Base;}for(int i=1;i<n+m;i++){c[i]+=c[i-1]/Base;c[i-1]%=Base;}while(c.size()>1u&&!c.back())c.pop_back();return c;}friend istream& operator>>(istream& is,BigInteger& a){string s;cin>>s;int n=s.size();per(j,n-1,0)a.pb(s[j]-'0');return is;}friend ostream& operator<<(ostream& os,BigInteger& a){int n=a.size();per(j,n-1,0)print(a[j]);return os;}
}BigInteger;const int N=2e5+5;
pii a[N];int T,n,p[N],sz[N],l[N],r[N],pos[N],vis[N];
int num,getmax,ans;
int find(int x){if(p[x]^x)p[x]=find(p[x]);return p[x];
}
int getmx(int x){return (((1<<(l[x]&1))|(1<<(r[x]&1)))&pos[x]);}
void merge(int x,int y){x=find(x); y=find(y);getmax-=getmx(x); getmax-=getmx(y);tomin(l[x],l[y]); tomax(r[x],r[y]);pos[x]|=pos[y]; getmax+=getmx(x);num-=(sz[x]+1>>1); num-=(sz[y]+1>>1);sz[x]+=sz[y]; num+=(sz[x]+1>>1);p[y]=x;
}
void solve(){cin>>n; rep(i,0,n+1)p[i]=l[i]=r[i]=i,sz[i]=1,pos[i]=vis[i]=0;num=getmax=ans=0; rep(i,1,n)cin>>a[i].fi,a[i].se=i; sort(a+1,a+1+n);per(i,n,1)if(a[i].fi==a[n].fi)pos[a[i].se]|=(1<<(a[i].se&1));per(i,n,1){int now=a[i].fi,id=a[i].se;vis[id]=1; getmax+=getmx(id), ++num;if(vis[id-1]) merge(id,id-1);if(vis[id+1]) merge(id,id+1);tomax(ans,a[n].fi+now+num-(!getmax));}cout<<ans<<'\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>T; while(T--) solve();return 0;
}