# 描述

Chiaki has a sequence $A={a_1,a_2,\dots,a_n}$. Let $\mathbf{RMQ}(A, l, r)$ be the minimum $i$ ($l \le i \le r$) such that $a_i$ is the maximum value in $a_l, a_{l+1}, \dots, a_{r}$.

Two sequences $A$ and $B$ are called RMQ Similar, if they have the same length n and for every $1 \le l \le r \le n$, $\mathbf{RMQ}(A, l, r) = \mathbf{RMQ}(B, l, r)$.

For a given the sequence $A={a_1,a_2,\dots,a_n}$, define the weight of a sequence $B={b_1,b_2,\dots,b_n}$ be $\sum\limits_{i=1}^{n} b_i$ (i.e. the sum of all elements in $B$) if sequence $B$ and sequence $A$ are RMQ Similar, or $0$ otherwise. If each element of $B$ is a real number chosen independently and uniformly at random between $0$ and $1$, find the expected weight of $B$.

## Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 10^6$) – the length of the sequence.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) denoting the sequence.
It is guaranteed that the sum of all $n$ does not exceed $3 \times 10^6$.

## Output

For each test case, output the answer as a value of a rational number modulo $10 ^ 9 + 7$.
Formally, it is guaranteed that under given constraints the probability is always a rational number pq ($p$ and $q$ are integer and coprime, $q$ is positive), such that $q$ is not divisible by $10 ^ 9 + 7$. Output such integer a between $0$ and $10 ^ 9 + 6$ that $p −aq$ is divisible by $10 ^ 9 + 7$.

# 思路

• 考虑到$B$中的元素是实数，因此元素相同的概率为$0$。可以假设是一个排列。
• $[0,1]$内随机一个实数的期望是$\frac{1}{2}$，那么一个排列的期望就是$\frac{n}{2}$。
• 问题等价于：$B$为$n$的一个全排列，满足RMQ形态和$A$相同的方案数$s$。那么答案就是$\frac{s}{n!} \times \frac{n}{2}$。
• RMQ形态相同即两者的笛卡尔树形态相同。
• 符合条件的数量就是$B$数组元素的全序数量，即树的拓扑序的数量：$\frac{n!}{\prod sz_i}$。
• 于是答案为：$\frac{n}{2\prod sz_i}$ ($sz_i$表示以$i$为根的子树的大小)

0%