// SOUMYAJEET GHATAK
// FOLLOW THE PATH OF A RIGHTEOUS MAN
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <limits>
#include <iomanip>
#include <functional>
#include <utility>
#include <cctype>
#include <cassert>
#include <climits>
using namespace std;
 
#define FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr);
#define int long long
 
#define vl vector<long long>
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rep(i,n) for(int i=0;i<n;i++)
#define invl(v,n) rep(i,n) cin>>v[i];
 
bool solve(int mid, vl& arr, int n, map<int,int>& mp,vl& pref){
 
    if(!mp.empty() && mp.rbegin()->first >= mid){
        return true;
    }
 
    int x = mid;
    map<int,int> mp2=mp;
 
    for(int i = n-1; i >= 1; i--){
 
        mp2[pref[i-1]]--;
 
        if(mp2[pref[i-1]] == 0){
            mp2.erase(pref[i-1]);
        }
 
        if(arr[i] >= x) x--;
        else if(arr[i] < x) x++;
 
        if(x==0) return true;
 
        if(!mp2.empty() && mp2.rbegin()->first >= x){
            return true;
        }
    }
 
    return false;
}
 
void _Soumya_(){
 
    int n;
    cin>>n;
 
    vl arr(n);
    invl(arr,n);
 
    vl pref(n);
 
    int x = 0;
 
    rep(i,n){
        if(arr[i] > x) x++;
        else if(arr[i] < x) x--;
        pref[i] = x;
    }
 
    map<int,int> mp;
 
    for(int i=0;i<n-1;i++){
        mp[pref[i]]++;
    }
    int s = 0;
    int e = n-1;
    int ans = 0;
 
    while(s <= e){
 
        int mid = (s+e)/2;
 
        if(solve(mid,arr,n,mp,pref)){
            ans = mid;
            s = mid+1;
        }
        else{
            e = mid-1;
        }
    }
 
    cout<<ans<<"\n";
}
 
signed main(){
 
    FAST_IO
 
    int t;
    cin>>t;
 
    while(t--){
        _Soumya_();
    }
 
    return 0;
}