#include #include #include #define LL long long #define Re register int using namespace std; const int N=25003,M=27; int n,K,A[N];LL dp[M][N]; inline void in(Re &x){ int f=0;x=0;char ch=getchar(); while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=f?-x:x; } struct BIT{ int nowL,nowR,C[N];LL ans; inline void add(Re x,Re v){if(!x)return;while(x<=n)C[x]+=v,x+=x&-x;} inline int ask(Re x){Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;} inline LL calc(Re L,Re R){ while(nowRL)--nowL,ans+=nowR-nowL-ask(A[nowL]),add(A[nowL],1); while(nowR>R)add(A[nowR],-1),ans-=ask(A[nowR]-1),--nowR; while(nowLr)return;Re mid=l+r>>1,w=0;LL tmp; for(Re j=L;j<=R&&j