#include #include #include #define LL long long #define Re register int using namespace std; const int N=1e5+3,M=23; 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 MODUI{ int nowL,nowR,cnt[N];LL ans; inline LL calc(Re L,Re R){ while(nowRL)--nowL,ans+=cnt[A[nowL]]++; while(nowR>R)ans-=--cnt[A[nowR]],--nowR; while(nowLr)return;Re mid=l+r>>1,w=0;LL tmp; for(Re j=L;j<=R&&j