1 #include <cstdio>
2 #include <cstring>
3 #define N 100005
4 5 int d[N], a[N], b[N], n, aa[N], bb[N], t1[N], t2[N];
6 7 int bs(
int x,
int len)
8 {
9 int l =
1, r = len, mid;
10 while(l<r)
11 {
12 mid = (l + r) /
2;
13 if(x<a[mid]) r = mid;
14 else if(x>=a[mid]) l = mid +
1;
15 }
16 return l;
17 }
18 19 int bs2(
int x,
int len)
20 {
21 int l =
1, r = len, mid;
22 while(l<r)
23 {
24 mid = (l + r) /
2;
25 if(x>b[mid]) r = mid;
26 else if(x<=b[mid]) l = mid +
1;
27 }
28 return l;
29 }
30 31 int main()
32 {
33 int t;
34 scanf(
"%d",&t);
35 while(t--)
36 {
37 memset(t1,
0,
sizeof(t1));
38 memset(t2,
0,
sizeof(t2));
39 scanf(
"%d",&n);
40 for(
int i=
1; i<=n; i++)
41 scanf(
"%d",&d[i]);
42 int len1 =
1;
43 a[
1] = d[n];
44 aa[n] =
1;
45 for(
int i=n-
1; i>=
1; i--)
46 {
47 if(d[i]>=a[len1])
48 {
49 a[++len1] = d[i];
50 aa[i] = len1;
51 }
52 else 53 {
54 int pos = bs(d[i],len1);
55 aa[i] = pos;
//前i个数的最长不降子序列长度为pos
56 a[pos] = d[i];
57 }
58 }
59 60 int len2 =
1;
61 b[
1] = d[n];
62 bb[n] =
1;
63 for(
int i=n-
1; i>=
1; i--)
64 {
65 if(d[i]<=b[len2])
66 {
67 //printf("b:%d\n",i);
68 b[++len2] = d[i];
69 bb[i] = len2;
70 }
71 else 72 {
73 int pos = bs2(d[i],len2);
74 bb[i] = pos;
75 b[pos] = d[i];
76 }
77 }
78 int ans =
0, aid = -
1;
79 for(
int i=
1; i<=n; i++)
80 {
81 int tmp = aa[i] + bb[i] -
1;
82 if(ans<tmp)
83 {
84 ans = tmp;
85 aid = i;
86 }
87 }
88 89 for(
int i=aid+
1; i<=n; i++)
90 {
91 if(d[i]==d[aid])
92 {
93 t1[aa[aid]-aa[i]]++;
94 t2[bb[aid]-bb[i]]++;
95 }
96 }
97 for(
int i=
1; i<=n; i++)
98 {
99 if(t1[i]==
1 && t2[i]==
1) ans--;
100 }
101 printf(
"%d\n",ans);
102 }
103 return 0;
104 }
