题意：定义一个数列A的\(RMQ(A,l,r)\)为使得\(a_i\)为\(a_l,a_{l+1},a_{l+2}, \cdots ,a_r\)中最大数的最小的i。
对于两个数列A与B，定义它们RMQ相似当且仅当两数列元素个数相等且对于所有的\(1 \leq l \leq r \leq n\)，有\( RMQ(A,l,r)=RMQ(b,l,r)\)。
现在给你一个正整数数列\(\{a_i\}\)，其中\(1 \leq a_i \leq n\)，对于实数数列\(\{b_i\}\)，其中\(b_i\)为\([0…1]\)中随机的一个实数，当数列A与B RMQ相似时，B的权值为\(\sum{b_i}\)，否则为0,求B权值的期望。（答案对\(10^9 + 7\)取模）（\(1 \leq n \leq 10^6\)）
题解：首先要观察两个序列RMQ相似的条件。当数列A是一个1..n的全排列时，两个序列RMQ相似当且仅当B中元素的大小顺序和A相同。此时答案为\(\frac{n}{2} \cdot \frac{1}{n!}\)（其中\(\frac{n}{2}\)表示的是B中元素之和的期望，\(\frac{1}{n!}\)表示的是B中元素大小顺序满足条件的概率）。
问题主要是在于当A中含有相同元素的时候的答案。由于不同的A的全排列所对应的满足条件的B是互不相交的（元素间大小关系不同），所以我们要求出与A RMQ相似的n排列的个数，答案就是这个乘上上面所说的一个排列所对应的答案。接下来找符合条件的全排列（记为C）的个数。
考虑A的一个区间\([l..r]\)，设\(m=RMQ(A,l,r)\)，那么我构造的\(c_m\)一定是C中该区间中的最大值，\(c_m\)的值可以确定下来。可以发现，当取任意的\(l \leq l_0 \leq m\)与\(m \leq r_0 \leq r\)的时候，\(RMQ(C,l_0,r_0)=RMQ(A,l_0,r_0)\)肯定是等于m的，也就是说此时m左右两边的数无论大小关系如何都互不影响，那么我们可以任意分配\(m-l\)个数给左边的区间，\(r-m\)个数给右边的区间，方案数为\(C_{r-l}^{m-l}\)，然后递归处理左右两个区间，最后再乘上两个区间的答案就好了。
由于n有\(10^6\)，直接DFS会爆栈。不过BFS写也不麻烦。求区间RMQ我直接用线段树来写了（ST表被卡内存），1200ms勉强还是跑过去了。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10,mo=1e9+7;
struct Segment_Tree
{
int v[maxn];
int maxpos[maxn<<2];
int n;
#define ls (o<<1)
#define rs ((o<<1)|1)
#define mid ((l+r)>>1)
int GetMaxpos(int a,int b)
{
if (v[a]==v[b]) return a;
else if (v[a]>v[b]) return a;
else return b;
}
void BuildTree(int o,int l,int r,int *a)
{
if (l==r)
{
maxpos[o]=l;
v[l]=a[l];
return;
}
BuildTree(ls,l,mid,a);
BuildTree(rs,mid+1,r,a);
maxpos[o]=GetMaxpos(maxpos[ls],maxpos[rs]);
}
int Query(int o,int l,int r,int a,int b)
{
if (a<=l && r<=b) return maxpos[o];
int res=a;
if (a<=mid) res=GetMaxpos(res,Query(ls,l,mid,a,b));
if (b> mid) res=GetMaxpos(res,Query(rs,mid+1,r,a,b));
return res;
}
int Query(int l,int r) {return Query(1,1,n,l,r);}
void Build_Tree(int _n,int *a) {n=_n;BuildTree(1,1,_n,a);}
#undef ls
#undef rs
#undef mid
}T;
long long p[maxn];
long long inv[maxn],invp[maxn];
int a[maxn];
int n;
long long C(int a,int b)
{
return (p[a]*invp[b]%mo)*invp[a-b]%mo;
}
void Init()
{
p[0]=1;
inv[1]=inv[0]=invp[0]=invp[1]=1;
for (int i=1;i<=1000000;i++) p[i]=p[i-1]*i%mo;
for (int i=2;i<=1000000;i++) inv[i]=(mo-mo/i)*inv[mo%i]%mo,invp[i]=invp[i-1]*inv[i]%mo;
}
int L[maxn],R[maxn];
long long Solve()
{
long long res=1;
int tot=1;
L[1]=1,R[1]=n;
for (int i=1;i<=n;i++)
{
int l=L[i],r=R[i];
if (l==r) continue;
int x=T.Query(l,r);
res=(res*C(r-l,x-l))%mo;
if (l<=x-1) L[++tot]=l,R[tot]=x-1;
if (x+1<=r) L[++tot]=x+1,R[tot]=r;
}
return res;
}
int main()
{
Init();
int Case;
scanf("%d",&Case);
while (Case--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
T.Build_Tree(n,a);
printf("%lld\n",(Solve()*invp[n-1]%mo)*inv[2]%mo);
}
return 0;
}