#include "bits/stdc++.h" using namespace std; #define all(x) x.begin(), x.end() void solve() { // INPUT int n; cin >> n; vector<int> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; } // lis stores the current lis // pref stores the longest increasing subsequence till i vector<int> lis, pref(n); for (int i = 0; i < n; i++) { auto it = lower_bound(all(lis), v[i]) - lis.begin(); if (it == lis.size()) lis.push_back(v[i]); else lis[it] = v[i]; pref[i] = lis.size(); } lis.clear(); // suff stores the longest increasing subsequence starting from i vector<int> suff(n); for (int i = n - 1; i >= 0; i--) { auto it = lower_bound(all(lis), -v[i]) - lis.begin(); if (it == lis.size()) lis.push_back(-v[i]); else lis[it] = -v[i]; suff[i] = lis.size(); } int ans = suff[0]; for (int i = 1; i < n; i++) { ans = max(ans, suff[i] + pref[i - 1]); } cout << ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); int tt = 1; cin >> tt; while (tt--) { solve(); cout << '\n'; } return 0; }