思路是：

1.奇数的话，找到中位数的位置，不断向左右扩展，扩展不了输出 答案

2.偶数的话，从两个中位数开始往两边扩展，扩展不了时输出答案，并加上中间的数。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>      
#include <string>
#include <queue>
#include <cstring>
#include <assert.h>
#include <map>
#define N 300005
using namespace std;
int t,n;
struct node{
	int id,val;
	bool operator <(const node &b)const{
		return val<b.val;
	}
}a[N],b[N];
void clr(int n){
	for(int i=1;i<=n;++i){
		a[i].val=a[i].id=b[i].val=b[i].id=0;
	}
} 
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;++i){
			cin>>a[i].val;
			a[i].id=i;
			b[i].val=i;
			b[a[i].val].id=i;
		}
		if(n&1){
			int mu=b[n/2+1].id;
			int l=mu,r=mu,zhen_l=n/2+1,zhen_r=n/2+1;
			while(1){
				--l;
				++r;
				if(l<1||r>n){
					++l;
					--r;
					break;
				}
				--zhen_l;
				++zhen_r;
				if(zhen_l<1||zhen_r>n){
					++l;
					--r;
					break;
				}
				if(a[l].val!=b[zhen_l].val||a[r].val!=b[zhen_r].val){
					++l;
					--r;
					break;
				}
			}
			cout<<(n-(r-l+1))/2;
		}
		else{
			int l=b[n/2].id+1,r=b[n/2+1].id-1,zhen_l=n/2+1,zhen_r=n/2;
			if(b[n/2+1].id<b[n/2].id){
				cout<<n/2<<'\n';
				clr(n);
				continue;
			}
//			cout<<b[n/2].id<<' '<<b[n/2+1].id<<'\n';
			while(1){
				--l;
				++r;
				if(l<1||r>n){
					++l;
					--r;
					break;
				}
				--zhen_l;
				++zhen_r;
				if(zhen_l<1||zhen_r>n){
					++l;
					--r;
					break;
				}
//				cout<<l<<' '<<r<<" "<<zhen_l<<' '<<zhen_r<<'\n';
				if(a[l].val!=b[zhen_l].val||a[r].val!=b[zhen_r].val){
					++l;
					--r;                              
					break;
				}
			}
//			cout<<l<<' '<<r<<'\n';
			cout<<(n-(r-l+1)+b[n/2+1].id-b[n/2].id-1)/2;
		}
		clr(n);
		cout<<'\n';
	}
	return 0;
}
//13 600
// 1 2 3 6 4 5