哇自闭了。
一样个毛啊。
和之前见过的几道感觉很类似啊。
首先一个数如果有贡献那么在他后面一定有一个大于它的数，并且前面的全比他小，然后我就跑偏了。。。
于是我们先排个序，显然无影响，我们可以考虑从 n 个位置里选择 n-i+1 个，用来存放 大于等于他自己的数，
这n-i+1个位置要保证 他自己在最前面吧，就是 (n-i)! 种，剩下i-1个位置随便放，(i-1)!
所以一个数的贡献次数 就是 C(n,n-i+1)*(i-1)!*(n-i)!，然后再乘上权值和次数就阔以惹qwq
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+;
const ll mod = 1e9+;
int n;ll a[N];
ll up[N],inv[N],down[N];
void init(){
inv[]=down[]=up[]=;
for(int i=;i<=1e6;i++){
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
for(int i=;i<=1e6;i++){
up[i]=up[i-]*i%mod;
down[i]=down[i-]*inv[i]%mod;
}
}
int main(){
//ios::sync_with_stdio(false);
init();
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
sort(a+,a++n);
ll ans=;
for(int i=,j;i<=n;i=j+){
j=i;
while (a[j+]==a[i])j++;
if(j<n)
ans=(ans+a[i]*(j-i+)%mod*up[n]%mod*up[n-i]%mod*up[i-]%mod*down[n-i+]%mod*down[i-]%mod)%mod;
}
cout<<ans<<endl;
}