小Z这个学期考了n次试，每一次都有一个在[0~20000]的整数分数。小Z本来的状态应该是每一次考试都比前一次多一分（除第一次），但由于他很不稳定，偏差可能很大。对于第i次考试，如果有第j次考试满足：1<=j<i<=n且以第j次考试分数作为基准，估计的第i次考试成绩比实际成绩低，就说第i次考试鄙视了第j次考试（估计分可以超过20000）。为了提高自信，小Z想知道他这个学期所有考试总共有多少次鄙视。

输入

第一行n（1<n<=100000） 第二行为n次考试成绩。

输出

一行，这个学期所有考试的总共鄙视次数，总数可能很大，只需要输出它mod 12345。

样例输入

4

1 3 3 5

样例输出

3

#include<bits/stdc++.h>
using namespace std;
int n,ans=0,a[100001],i,b[100001];
int MOD=12345;
void Merge(int l,int r)
{
	if(l>=r)return;
	int mid=(l+r)/2;
	Merge(l,mid);
	Merge(mid+1,r);
	int i=l,j=mid+1;
		for(int k=l;k<=r;k++)
			if(a[i]<a[j]&&i<=mid||j>r){
				if(j<=r)ans=(ans+r-j+1)%MOD;
					b[k]=a[i++];
			}
		else b[k]=a[j++];
		for(int k=l;k<=r;k++){
			a[k]=b[k];
		}
}
int main()
{
	cin>>n;
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	Merge(1,n);
	cout<<ans;
	return 0;
}