设$f_i$表示$i$排列的数量，其中$x$表示不确定
那么$$ans=f_{1324}-f_{1432}-f_{1243}=(f_{1x2x}-f_{1423})-(f_{14xx}-f_{1423})-(f_{12xx}-f_{1234})$$
$$=f_{1x2x}-(f_{14xx}+f_{12xx})+f_{1234}$$
$$=f_{1x2x}-f_{1xxx}+f_{13xx}+f_{1234}$$
①$f_{1xxx}$用树状数组求正序对
②$f_{1234}$四个树状数组瞎搞
③$f_{1x2x}$，考虑枚举$2$的位置
设$l_i$表示满足$j<i,a_j<a_i$的$j$的数量，$r_i$表示满足$j>i,a_j<a_i$的$j$的数量
那么右边的$x$的取法就是$N-i-r_i$种
考虑左边的$x$，考虑容斥。满足$p<i,q<i,a_p<a_i$的有序数对$(p,q)$的数量有$l_i \times (i-1)$个，但是其中多算了：
a.$p<q , a_q<a_i$，个数有$C_{l_i}^2$个
b.$p \geq q$，个数有$\sum j[j < i,a_j<a_i]$种
④$f_{13xx}$，考虑枚举$3$的位置，那么右边的$4$的取法有$N-i-r_i$种
仍然考虑容斥。满足$a_p<a_i , a_q < a_i , p < i$的个数为$(a_i-1) \times l_i$
考虑多算了什么：
a.$a_q > a_p , q < i$，有$C_{l_i}^2$种
b.$a_q \leq a_p$，有$\sum a_j[j < i , a_j < a_i]$种
上面四种加起来就行了
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
, MOD = ;
int num[MAXN] , N , sum;
namespace calc{
][MAXN] , l[MAXN] , r[MAXN];
inline int lowbit(int x){
return x & -x;
}
inline void add(int ver , int dir , int num){
while(dir <= N){
(Tree[ver][dir] += num) %= MOD;
dir += lowbit(dir);
}
}
inline int get(int ver , int dir){
;
while(dir){
(sum += Tree[ver][dir]) %= MOD;
dir -= lowbit(dir);
}
return sum;
}
void calc_1xxx(){
for(int i = N ; i ; --i){
, num[i]);
sum = (sum - t * (t - ) * (t - ) / % MOD + MOD) % MOD;
add( , num[i] , );
}
}
void calc_1234(){
; i <= N ; ++i){
sum = (sum + , num[i])) % MOD;
add( , num[i] , , num[i]));
add( , num[i] , , num[i]));
add( , num[i] , );
}
memset(Tree , , sizeof(Tree));
}
void calcl(){
; i <= N ; ++i){
l[i] = , num[i]);
add( , num[i] , );
}
}
void calcr(){
for(int i = N ; i ; --i){
r[i] = , num[i]);
add( , num[i] , );
}
}
void calc_1x2x(){
; i <= N ; ++i){
) - 1ll * l[i] * (l[i] - ) / - , num[i])) % MOD;
sum = (sum + times * base) % MOD;
add( , num[i] , i);
}
}
void calc_13xx(){
; i <= N ; ++i){
) - 1ll * l[i] * (l[i] - ) / - , num[i])) % MOD;
sum = (sum + times * base) % MOD;
add( , num[i] , num[i]);
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("4528.in" , "r" , stdin);
//freopen("4528.out" , "w" , stdout);
#endif
N = read();
; i <= N ; ++i)
num[i] = read();
calc::calc_1xxx();
calc::calc_1234();
calc::calcl();
calc::calcr();
calc::calc_1x2x();
calc::calc_13xx();
cout << sum;
;
}