我想到按aia_iai​排序，设bib_ibi​表示第iii个位置对应的排名，这样总方案数∏i=1n(ai−i+1)\prod_{i=1}^n{(a_i-i+1)}∏i=1n​(ai​−i+1)。

固定pbi=xp_{b_i}=xpbi​​=x，那么若jjj对答案有贡献，应该满足：

1.11.11.1 bj>bi，pbjb_i，p_{b_j}bi​，pbj​​

那么，令aj←min⁡(x−1,aj)a_j\gets \min(x-1,a_j)aj​←min(x−1,aj​)然后算挖掉xxx后的方案数即可。

瞪眼大法可知，当aiaja_i>a_jai​>aj​的情况反过来容斥即可。

考虑优化。注意到我们已经按aia_iai​排序了，那么从后往前遍历，线段树上每个点存的是变成aia_iai​后的方案数，考虑从aia_iai​再变到ai−1a_{i-1}ai−1​时，相对位置没有发生变化，那么相当于全局乘一个固定数，线段树查询bib_ibi​以后的部分即可。

复杂度O(nlog⁡n)O(n\log n)O(nlogn)。

#include
#define fi first
#define se second
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int mod=1e9+7;
ll pw(ll x,ll y=mod-2){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
int n;
ll bit[200005],bit1[200005],res,M,M2,inv2(pw(2));
vector>v;
struct node{int a,b;bool operator <(const node &r)const{return av.pb({x,y});for(;x<=n;x+=x&-x)bit[x]=(bit[x]+y)%mod,bit1[x]++;
}
ll qry(int x){ll tot(0);for(;x;x-=x&-x)tot=(tot+bit[x])%mod;return tot;
}
ll qry2(int x){ll tot(0);for(;x;x-=x&-x)tot+=bit1[x];return tot;
}
void cl(){for(auto x:v){int y=x.fi,z=x.se;for(;y<=n;y+=y&-y)bit[y]=(bit[y]-z)%mod; }v.clear();
}
int rev(int x){return n-x+1;
}
ll solve(){ll tot(0);M=1;for(int i=n;i>=1;i--){int j=i;while(s[j-1].a==s[i].a)j--;if(s[i].a==i)cl(),M=1;else if(i!=n)M=M*pw(s[i+1].a-i)%mod*(s[i].a-i)%mod;for(int k=j;k<=i;k++){tot+=qry(rev(s[k].b))*M%mod*inv2%mod,tot%=mod;}for(int k=j;k<=i;k++){add(rev(s[k].b),M2*pw(M)%mod);}i=j;}cl(),M=1;memset(bit1,0,sizeof bit1);for(int i=n;i>=1;i--){int j=i;while(s[j-1].a==s[i].a)j--;if(s[i].a==i)cl(),M=1;else if(i!=n)M=M*pw(s[i+1].a-i)%mod*(s[i].a-i)%mod;for(int k=j;k<=i;k++){tot+=qry2(s[k].b)*M2%mod,tot-=qry(s[k].b)*M%mod*inv2%mod,tot%=mod; }for(int k=j;k<=i;k++){add(s[k].b,M2*pw(M)%mod);}i=j;}return tot; 
}
signed main(){cin>>n;for(int i=1;i<=n;i++)cin>>s[i].a,s[i].b=i;sort(s+1,s+1+n);M2=1;for(int i=1;i<=n;i++)M2=M2*(s[i].a-i+1)%mod;if(!M2){cout<<0;return 0;}for(int i=1;i<=n;i++){int j=i;while(s[j+1].a==s[i].a)j++;res+=M2*inv2%mod*(j-i+1)%mod*(j-i)%mod*inv2%mod,res%=mod;i=j;}res+=solve(),res%=mod;cout<<(res+mod)%mod;
}