设 \(f_i\) 表示以第 \(i\) 个结尾，强制选第 \(i\) 个所能得到的最长几乎上升序列的长度。
则 \(f_i=\max\limits_{j\lt i,a_j\le a_i}\left\{f_j+1+w(i,j)\right\}\)。
其中 \(w(i,j)=0/1\) 表示 \([j+1,i-1]\) 有没有比 \(a_i\) 和 \(a_j\) 都大的数。
对于每个 \(i\) 用单调栈预处理出 \(pre_i\) 表示 \(i\) 左边第一个大于 \(a_i\) 的位置，没有则为 \(0\)。
则 \(f_i=\max(\max\limits_{j\lt pre_i,a_j\le a_i}\left\{f_j\right\}+2,\max\limits_{pre_i\le j\lt i,a_j\le a_i}\left\{f_j\right\}+1)\)。
将 \(a\) 从小到大排序后依次加入，发现涉及到的操作有求前缀 \(\max\)，单点修改，用树状数组维护即可。
具体细节看代码。
Code：
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair <int, int> pii;
const int N = 500005;
int T;
int n;
pii a[N]; int stk[N], top;
int f[N], pre[N];
int c[N];
void upd(int x, int y) { for (; x <= n; x += x & -x) c[x] = max(c[x], y); }
int query(int x) { int res = 0; for (; x; x -= x & -x) res = max(res, c[x]); return res; }
void solve() {
scanf("%d", &n);
memset(c + 1, 0, sizeof (int) * n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i].fi), a[i].se = i;
top = 0;
for (int i = 1; i <= n; ++i) {
while (top && a[stk[top]] <= a[i]) --top;
pre[i] = stk[top], stk[++top] = i;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) {
int _ = a[i].se;
f[_] = query(_ - 1) + 1;
if (pre[_]) f[_] = max(f[_], query(pre[_] - 1) + 2);
upd(_, f[_]);
}
printf("%d\n", query(n));
}
int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}