#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef __int128_t INT;
const int N=2e5+9;
const LL P=1e18+3;
int n,p[N];
struct node{
	int v; LL c;
}E,I,tr[N],a[N],b[N],c[N],d[N];
node operator+(node a,node b){
	if(a.v^b.v) return a.v>b.v?a:b;
	return {a.v,(a.c+b.c)%P};
}
void cl(){
	for(int i=1;i<=n;i++) tr[i]=E;
}
void add(int x,node c){
	for(;x<=n;x+=x&-x) tr[x]=tr[x]+c;
}
node query(int x){
	node res=E;
	for(;x;x&=x-1) res=res+tr[x];
	return res;
}
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&p[i]);
	cl(); for(int i=1;i<=n;i++) a[i]=query(p[i]),a[i].v++,a[i]=a[i]+I,add(p[i],a[i]);
	cl(); for(int i=1;i<=n;i++) b[i]=query(n-p[i]+1),b[i].v++,b[i]=b[i]+I,add(n-p[i]+1,b[i]);
	cl(); for(int i=n;i;i--) c[i]=query(p[i]),c[i].v++,c[i]=c[i]+I,add(p[i],c[i]);
	cl(); for(int i=n;i;i--) d[i]=query(n-p[i]+1),d[i].v++,d[i]=d[i]+I,add(n-p[i]+1,d[i]);
	node t1=E,t2=E;
	for(int i=1;i<=n;i++) t1=t1+a[i],t2=t2+b[i];
	LL r2=(INT)t1.c*t2.c%P; int r1=t1.v+t2.v;
	for(int i=1;i<=n;i++) if(a[i].v+b[i].v+c[i].v+d[i].v-3==r1-1) r2=(r2-(INT)a[i].c*b[i].c%P*c[i].c%P*d[i].c%P+P)%P;
	if(r2) printf("%d\n",r1);
	else printf("%d\n",r1-1);
}
int main(){
	E={-1,0},I={1,1};
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}