#include<bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; usingnamespace std; #define ll long long #define ull unsigned ll constint N = 5e5 + 10; constint INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9 + 7; const ll inv2 = (mod + 1) / 2; int T; int n; int a[N]; int r[N]; int st[N], tp; int dp[N], dp2[N]; int mx[N]; voidupd(int q, int x){ for (int i = q; i <= n; i += (i&-i))mx[i] = max(mx[i], x); } intqry(int r){ int ans = 0; for (int i = r; i; i -= (i&-i))ans = max(ans, mx[i]); return ans; } int mx2[N]; voidupd2(int q, int x){ for (int i = q; i <= n; i += (i&-i))mx2[i] = max(mx2[i], x); } intqry2(int r){ int ans = 0; for (int i = r; i; i -= (i&-i))ans = max(ans, mx2[i]); return ans; } vector<int>vc[N]; intmain(){ scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++)scanf("%d", &a[i]); tp = 0; a[n + 1] = INF; st[++tp] = n + 1; for (int i = 1; i <= n + 1; i++)vc[i].clear(); for (int i = n; i >= 1; i--) { while (tp&&a[st[tp]] <= a[i])tp--; r[i] = st[tp]; vc[r[i]].push_back(i); st[++tp] = i; } fill(mx, mx + n + 1, 0); fill(mx2, mx2 + n + 1, 0); fill(dp, dp + n + 1, 0); fill(dp2, dp2 + n + 1, 0); for (int i = 1; i <= n; i++) { dp2[i] = dp[a[i]] = max(dp[a[i]], qry(a[i]) + 1); if (i > 1)dp2[i] = dp[a[i]] = max(dp2[i], qry2(a[i]) + 2); upd(a[i], dp[a[i]]); for (int u : vc[i])upd2(a[u], dp2[u]); } int ans = 0; for (int i = 1; i <= n; i++)ans = max(ans, dp2[i]); printf("%d\n", ans); } return0; }