题目：http://acm.hdu.edu.cn/showproblem.php?pid=6305
看题解，得知：
0~1内随机取实数，取到两个相同的数的概率是0，所以认为 b 序列是一个排列。
两个序列“RMQ相似”，意为它们的笛卡尔树同构。注意有相同值的时候，后出现的应该位于先出现的的子树中。
一个排列的笛卡尔树与给定笛卡尔树同构的概率是 \( \prod\limits_{i=1}^{n}\frac{1}{siz_i} \) ，其中 \( siz_i \) 表示树上编号为 i 的点的子树大小。
不过不太明白为什么是这样。
一个数的期望值是 \( \frac{1}{2} \) ，所以整个序列的期望值就是 \( \frac{n}{2} \) ，乘上刚才那个同构概率即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
const int N=1e6+,mod=1e9+;
int pw(int x,int k)
{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;} int n,a[N],ans,inv[N];
int sta[N],top,ls[N],rs[N],fa[N];
void init()
{
int n=1e6;
for(int i=;i<=n;i++)inv[i]=pw(i,mod-);
}
void get_dkr()
{
top=;
for(int i=;i<=n;i++)
{
ls[i]=rs[i]=fa[i]=;
while(top&&a[sta[top]]<a[i])
ls[i]=sta[top--];
fa[i]=sta[top]; sta[++top]=i;
rs[fa[i]]=i; if(ls[i])fa[ls[i]]=i;
}
}
int dfs(int cr)
{
if(!cr)return ;
int siz=dfs(ls[cr])+dfs(rs[cr])+;
ans=(ll)ans*inv[siz]%mod;
return siz;
}
int main()
{
int T=rdn();init();
while(T--)
{
n=rdn();for(int i=;i<=n;i++)a[i]=rdn();
get_dkr(); ans=(ll)n*inv[]%mod; dfs(rs[]);
printf("%d\n",ans);
}
return ;
}