不妨令 $f_n$ 表示一个长度为 $n$ 的随机排列的 shuffle 次数的期望，那么答案就是

\[\sum_i f(r_i-l_i+1)+[l_i<r_i]\]

因为长度为 $1$ 的区间无需 shuffle。

令 $g_n$ 表示长度为 $n$ 的排列，满足其不能被划分为若干段的方案数，那么

\[H(x)=\sum_{i=0}^\infty i!x^i\\ n!=\sum_{i=1}^ng_i(n-i)!\\ H=1+H\ast G\\ G(x)=1-\frac1{H(x)}\]

可以使用多项式求逆或者分治 NTT 来计算 $g_n$。

现在考虑求 $f_n$，可以写出递推式

\[f_n=\sum_{i=1}^n\frac{g_i(n-i)!}{n!}(f_i+[i>1]+f_{n-i})\]

其中 $\frac{g_i(n-i)!}{n!}$ 表示第一段长度恰好为 $i$ 的概率。
我们这里只去计算第一段的贡献。注意，$f_n$ 表示的是一个随机排列的期望，所以我们只是相当于钦定了一个前缀，后面那部分的贡献的期望自然就是 $f_{n-i}$。

\[\begin{aligned} f_n&=\sum_{i=1}^n\frac{g_i(n-i)!}{n!}(f_i+[i>1]+f_{n-i})\\ &=1-\frac1n+\sum_{i=1}^n\frac{g_i(n-i)!}{n!}(f_i+f_{n-i})\\ &=1-\frac1n+\frac{g_nf_n}{n!}+\sum_{i=1}^{n-1}\frac{g_i(n-i)!}{n!}(f_i+f_{n-i})\\ \end{aligned}\]

移项

\[f_n=\frac1{n!-g_n}\left(n!-(n-1)!+\sum_{i=1}^{n-1}g_if_i(n-i)!+g_if_{n-i}(n-i)!\right)\]

分治 NTT 维护即可，可以在转移时记录一下多项式 $f_i\times g_i,f_i\times i!$ 方便转移。

constexpr int N=1e5+7;
int n,a[N];
poly F,G,H,FG,FH;
#define mid ((l+r)>>1)
void solve(int l,int r){
	if(l==r){
		F[l]+=H[l]-H[l-1];
		F[l]/=H[l]-G[l];
		FG[l]=F[l]*G[l];
		FH[l]=F[l]*H[l];
		return;
	}
	solve(l,mid);
	poly tmp;
	tmp.assign(FG.begin()+l,FG.begin()+mid+1);
	poly t1=poly(H.begin(),H.begin()+r-l+1)*tmp;
	tmp.assign(FH.begin()+l,FH.begin()+mid+1);
	poly t2=poly(G.begin(),G.begin()+r-l+1)*tmp;
	for(int i=mid+1;i<=r;i++)
		F[i]+=t1[i-l]+t2[i-l];
	solve(mid+1,r);
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n;
	FG.resize(n+1);
	FH.resize(n+1);
	H.assign(n+1,1);
	for(int i=1;i<=n;i++)H[i]=H[i-1]*i;
	G=-inV(H,n+1);G[0]+=1;
	F.resize(n+1);
	// for(int i=2;i<=n;i++){
	// 	for(int j=1;j<=i-1;j++)
	// 		F[i]+=G[j]*F[j]*H[i-j]+G[j]*F[i-j]*H[i-j];
	// 	F[i]+=H[i]-H[i-1];
	// 	F[i]/=H[i]-G[i];
	// }
	solve(1,n);
	for(int i=1;i<=n;i++)cin>>a[i];
	mint ans=0;
	for(int l=1,r=1;l<=n;l=r+1){
		int mn=a[l],mx=a[l];
		for(r=l;;r++){
			mn=min(mn,a[r]);
			mx=max(mx,a[r]);
			if(l==mn&&r==mx)break;
		}
		ans+=F[r-l+1];
		if(l<r)ans+=1;
	}
	cout<<ans;
	return 0;
}