总结 E1 的构造：维护集合 S 表示所有不在序列中出现过或者在 a_i 之前的大于 a_i 的数的集合，当 a_i>a_{i+1} 时任选一个不在 S 中的元素放下，当 a_i=a_{i+1} 时任选一个 S 中的元素放，并从 S 中移除这个元素。一些要求：对于 S 中的每个元素，要求其第一次出现位于某个位置之前。该要求值域上具有单调性。
显然，集合 S 内元素首次出现的位置集合恰好是所有满足 a_i=a_{i-1} 的 i，或者 i=1。我们不妨直接按照最晚出现位置的限制从紧到松每个安排。维护当前可用位置数量即可。
不难发现另一部分只与 S 的大小有关，过程中 S 的大小是好维护的，直接乘即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 200005
#define mod 1000000007
int n,a[MAXN],b[MAXN],vis[MAXN];
vector<int> T[MAXN];
inline void clear(){
for( int i = 0 ; i <= n + 1 ; i ++ ) a[i] = b[i] = vis[i] = 0,T[i].clear();
}
inline void solve(){
scanf("%lld",&n);
for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&a[i]),a[i] <= n ? vis[a[i]] ++ : 0;
if( a[1] != n && a[1] != n - 1 ){ puts("0"); clear(); return; }
a[0] = n + 1;
for( int i = n - 1 ; i >= 0 ; i -- ){
if( a[i] < a[i + 1] ){ puts("0"); clear(); return; }
if( a[i] > a[i + 1] )
for( int v = a[i + 1] + 1 ; v < a[i] ; v ++ ) T[i + 1].emplace_back( v );
}
int R = 0;
int ans = 1,c = 0,p = 0;
for( int i = 1 ; i <= n ; i ++ ){
if( i == 1 || a[i] == a[i - 1] ){
c ++,R ++;
//R 表示在被钦定位置集合上的数的个数
}
else{
p ++,ans = ans * ( R + p ) % mod;
}
for( int ele : T[i] ) ans = ans * c % mod,c --;
}
while( c ) ans = ans * c % mod,c --;
printf("%lld\n",ans);
clear();
}
//2 0/0 2
signed main(){
int t; scanf("%lld",&t);
while( t -- ) solve();
return 0;
}
```