传送门
首先可以将题意大概可以简化为：取两端不重复的连续子序列，组成一个最长的连续递增子序列。
我们先 dp 预处理出以 \(i\) 为结尾的连续递增子序列长度 \(dpr_{i}\)。
同样预处理出以 \(i\) 为开头的连续递增子序列长度 \(dpl_{i}\)。
考虑对于每个 \(dpr_{i}\)，找到满足 \(a_{j}<a_{i}\) 的最大的 \(dpl_{i}\)。
这个过程可以建一个桶，用二分查找来优化，但是问题来了：\(a_{i}\leq 10^9\)，用 \(a_{i}\) 当数组下标显然不行。
这里有一个常见的小技巧：将数值和下标互换，以 \(dpl_{i}\) 作为数组下标，最小的 \(a_{i}\) 作为数组存的值。
所以我们开一个 \(t\) 数组，\(t_{i}=j\) 表示长度为 \(i\) 的序列的结尾最小值为 \(j\)。对于每个 \(dpr_{i}\)，在这个数组中二分查找即可。
时间复杂度：\(\mathcal{O}(Tn\log{n})\)。
\(\mathcal{Code}\)：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define il inline
#define re register
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define F(i,a,b) for(re int (i)=(a);(i)<=(b);(i)++)
#define DF(i,a,b) for(re int (i)=(a);(i)>=(b);(i)--)
#define G(i,u) for(re int (i)=head[u];(i);(i)=nxt[(i)])
inline ll read(){ll 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<<3)+(x<<1)+ch-48;ch=getchar();}return x*f;}
const int N=200010;
int n;
int a[N],dpl[N],dpr[N],t[N];
int main()
{
int T=read();
while(T--)
{
memset(t,0x3f,sizeof(t));
n=read();
dpl[0]=dpl[n+1]=dpr[0]=dpr[n+1]=0;
a[0]=INF,a[n+1]=-INF;
F(i,1,n) a[i]=read();
F(i,1,n)
{
if(a[i]>a[i-1]) dpl[i]=dpl[i-1]+1;
else dpl[i]=1;
}
DF(i,n,1)
{
if(a[i]<a[i+1]) dpr[i]=dpr[i+1]+1;
else dpr[i]=1;
}
int ans=0;
F(i,1,n)
{
t[dpl[i]]=min(t[dpl[i]],a[i]);
int k=lower_bound(t+1,t+n+1,a[i])-t-1;
ans=max(ans,k+dpr[i]);
}
printf("%d\n",ans);
}
return 0;
}