1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 100000 + 10; 9 int n;10 int a1[maxn], a2[maxn * 2], p[maxn * 2];11 12 void Init(void)13 {14     int id, mx = 0, j = 2;15     a2[0] = -1, a2[1] = 0;16     for(int i = 0; i < n; ++i)17     {18         a2[j++] = a1[i];19         a2[j++] = 0;20     }21 }22 23 void Manacher(int a[])24 {25     int mx = 0, id;26     p[0] = 0;27     for(int i = 0; i < (n+1)*2; ++i)28     {29         if(mx > i)30             p[i] = min(p[id*2-i], mx-i);31         else32             p[i] = 1;33         while(a[i+p[i]] == a[i-p[i]])34         {35             if(a[i-p[i]])36             {37                 if(a[i-p[i]] <= a[i-p[i]+2])38                     ++p[i];39                 else40                     break;41             }42             else43                 ++p[i];44         }45         if(mx < i + p[i])46         {47             mx = i + p[i];48             id = i;49         }50     }51 }52 53 void getans(void)54 {55     int ans = 1;56     for(int i = 1; i < (n+1)*2; ++i)57         ans = max(ans, p[i] - 1);58     printf("%d\n", ans);59 }60 61 int main(void)62 {63     #ifdef LOCAL64         freopen("4513in.txt", "r", stdin);65     #endif66 67     int T;68     scanf("%d", &T);69     while(T--)70     {71         scanf("%d", &n);72         for(int i = 0; i < n; ++i)73             scanf("%d", &a1[i]);74         Init();75         Manacher(a2);76         getans();77     }78     return 0;79 }