/* ********************** ********************** *** ADIT SHAH *** *** DA-IICT *** *** adit19shah *** ********************** ********************** */ #include using namespace std; #define fr(x,s,e) for(ll x = s; x < e; ++x) #define ll long long int #define ld long double #define imx 1e18 #define imn -1e18 #define pb push_back #define pll pair #define vl vector #define ff first #define ss second #define bl bool #define tr true #define fl false #define all(v) v.begin(),v.end() #define eps 1e-9; //Epsilon value below which approximate floating type number as 0 //#define mod1 1000000007 #define mod1 998244353 #define jadap ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) //For implementing policy based Data Structure, ordered_set #include #include using namespace __gnu_pbds; #define ordered_set tree, rb_tree_tag,tree_order_statistics_node_update> void yno(bool ok) { if(ok) cout<<"YES\n"; else cout<<"NO\n"; } vl fact(100001); void pre(){ fact[0]=1,fact[1]=1; fr(i,2,100001){ fact[i]=(fact[i-1]*i)%mod1; fact[i]%=mod1; } } void solve(ll z){ ll n; cin>>n; vl v(n); fr(i,0,n) cin>>v[i]; if(n==1){ cout<<1<<"\n"; return; } vl p(n),s(n); ordered_set st; fr(i,0,n) st.insert(i); p[0]=v[0],s[n-1]=v[n-1]; fr(i,1,n) p[i]=min(v[i],p[i-1]); for(ll i=n-2;i>=0;i--) s[i]=min(v[i],s[i+1]); ll l,r; fr(i,0,n) if(!p[i]) {l=i;break;} for(ll i=n-1;i>=0;i--) if(!s[i]) {r=i;break;} vl u(n); st.erase(v[0]); st.erase(v[n-1]); st.erase(0); fr(i,1,l){ if(p[i]==p[i-1]){ ll a=0; while(p[i]==p[i-1]) i++,a++; u[p[i-1]]=a; i--; } else st.erase(v[i]); } for(ll i=n-2;i>r;i--){ if(s[i]==s[i+1]){ ll a=0; while(s[i]==s[i+1]) i--,a++; u[s[i+1]]=a; i++; } else st.erase(v[i]); } /*fr(i,0,n) cout<=0;i--){ if(u[i]){ ll op=(st.size()-st.order_of_key(i)); ans*=(fact[op]/fact[op-u[i]]); ans%=mod1; ll zz=u[i]; while(zz){ st.erase(prev(st.end())); zz--; } } } cout<>T; pre(); fr(z,0,T){ solve(z); } return 0; }