大体思路就是 dp。WA 61 pts。

#include<bits/stdc++.h>
using namespace std;
int n,f[2][10005][2],a[10005],maxn[10005],ans;
const int mod=1000007;
int main()
{
	//freopen("teams.in","r",stdin);
	//freopen("teams.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),maxn[i]=max(maxn[i-1],a[i]);
	//f[i][j][0/1]表示前 i 位，最大值为 j，是否顶到上界的方案数
	f[0][0][0]=1;
	for(int i=1;i<=n;i++)
	{
		int p=i&1;
		memset(f[p],0,sizeof(f[p]));
		for(int j=1;j<=maxn[i];j++)
		{
			if(j==a[i])f[p][j][0]=(f[p][j][0]+f[p^1][j-1][0])%mod,f[p][j][1]=(f[p][j][1]+f[p^1][j-1][1])%mod;
			else if(j>a[i])f[p][j][1]=(f[p][j][1]+f[p^1][j-1][1])%mod;
			else f[p][j][1]=(f[p][j][1]+f[p^1][j-1][1]+f[p^1][j-1][0])%mod;
			if(j>=a[i])f[p][j][0]=(f[p][j][0]+f[p^1][j][0])%mod,f[p][j][1]=(f[p][j][1]+1ll*j*f[p^1][j][1]%mod+1ll*(a[i]-1)*f[p^1][j][0]%mod)%mod;
			else f[p][j][1]=(f[p][j][1]+1ll*j*(f[p^1][j][0]+f[p^1][j][1])%mod)%mod;
		}
	} 
	for(int i=1;i<=maxn[n];i++)ans=(ans+f[n&1][i][1])%mod;
	printf("%d",(ans+1)%mod);
	return 0;
}