昨日%你赛题。

题目描述 小明和小名两个人都喜欢弹珠，虽然他们都各自拥有很多不同的弹珠，但他们也很想要对方的弹珠，于 是他们决定进行等价交换。他们把自己的弹珠都放在了一起并且排成了一排，两人的弹珠一共有n 颗。 为了方便观看，他们决定将弹珠按精美度从小到大进行排列。在排列过程中，只有相邻的弹珠才可以进 行交换。每产生一次交换，交换的两个弹珠就会产生破碎值。 如果某个弹珠第一次交换，则破碎值增加1，第二次再产生交换时破碎值增加2。依次类推，若该弹珠第k 次产生交换，则破碎值增加k 。 为了尽量减少破碎，请你帮助小明和小名计算，让所有弹珠从小到大排序后，产生的破碎值之和最小为 多少。 请注意：若两颗弹珠的精美度相等，则谁排前面都没有关系。

输入 第一行输入一个整数n ，表示弹珠的总数量 第二行输入n 个整数a[i] ，表示精美度为a[i] 的弹珠初始时在位置i 。

输出 输出一个数，表示排列后最小的破碎值之和。

#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
typedef long long ll;
constexpr int N=1e5+5;
int n,a[N],nxd,c[N],d[N];
ll calc(int x){
	return x*1ll*(x+1)/2;
}
void msort(int b,int e){
    if(b==e)  return;
    int mid=(b+e)/2,i=b,j=mid+1,k=b;
    msort(b,mid),msort(mid+1,e);
    while(i<=mid&&j<=e)
    	if(a[i]<=a[j]) c[k++]=a[i++];
    	else d[j]+=mid-i+1,d[i]+=mid-i+1,c[k++]=a[j++];
    while(i<=mid)c[k++]=a[i++];
    while(j<=e)c[k++]=a[j++];
    for(int l=b;l<=e;l++)a[l]=c[l];
} 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	msort(1,n);
	ll ans=0;
	for(int i=1;i<=n;i++) ans+=calc(d[i]);
	cout<<ans<<endl;
	return 0;
}