仔细观察容易想到设 \(f_{l,r,x,y}\) 表示限制了区间 \([l,r]\) 种只能取 \([x,y]\) 中的数期望取多少个，看一下转移发下可能对最终答案有贡献的 \([x,y]\) 只可能是 \([p_{l-1},p_{r+1}]\)
设 \(cnt\) 为区间 \([l,r]\) 内在 \([p_{l-1},p_{r+1}]\) 中的元素个数 我们有:
\[f_{l,r}=\begin{cases} &{1\over cnt}(\sum_{p_{l-1}<p_x<p_{r+1}} f_{l,x-1}+f_{x+1,r}) + 1 \space\space\space\space cnt>0 \\& 0 \space\space\space\space cnt=0\end{cases} \]考虑求和很像二维数点，但是一般的先枚举长度在枚举左端点是做不了的。区间dp还有一种不常用的枚举顺序是左端点从右往左，右端点从左往右枚举。这样每次能固定一个左端点，当前左端点以及每一个右端点开个树状数组即可，求 \(cnt\) 也是一样的。
#include <bits/stdc++.h>
using namespace std;
const int N = 2005, mod = 1e9 + 7;
inline int read() {
register int s = 0, f = 1; register char ch = getchar();
while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch & 15), ch = getchar();
return s * f;
}
inline int power(int a, int b) {
int t = 1, y = a, k = b;
while (k) {
if (k & 1) t = (1ll * t * y) % mod;
y = (1ll * y * y) % mod;
k >>= 1;
} return t;
}
int inv[N], n, p[N], f[N][N];
struct BIT {
int tree[N];
inline BIT() { }
inline void clear() {
memset(tree, 0, sizeof tree);
}
inline void add(int x, int k) {
++x;
for (int i = x; i <= n + 2; i += i & -i) {
tree[i] = (tree[i] + k) % mod;
if (tree[i] < 0) tree[i] += mod;
}
}
inline int sum(int x) {
int res = 0; ++x;
for (int i = x; i; i -= i & -i) {
res += tree[i];
if (res >= mod) res -= mod;
} return res;
}
} pre[N];
int main() {
// freopen("ex_is2.in", "r", stdin);// freopen("is.out", "w", stdout);
n = read();
for (int i = 1; i <= n; ++i) p[i] = read();
p[0] = 0; p[n + 1] = n + 1;
for (int i = 1; i <= n; ++i) inv[i] = power(i, mod - 2);
memset(f, 0, sizeof f); BIT cnt, L;
for (int i = n; i; --i) {
cnt.clear(); L.clear();
for (int j = i; j <= n; ++j) { //i-1 j + 1
cnt.add(p[j], 1);
L.add(p[j], f[i][j - 1]);
pre[j + 1].add(p[i], f[i + 1][j]);
int s = cnt.sum(p[j + 1]) - cnt.sum(p[i - 1]);
if (s <= 0) continue;
f[i][j] = (1ll * inv[s] * (L.sum(p[j + 1]) - L.sum(p[i - 1]) +
pre[j + 1].sum(p[j + 1]) - pre[j + 1].sum(p[i - 1])) + 1) % mod;
}
}
printf("%d\n", f[1][n]);
return 0;
}