/*
ZADATAK: reli
JEZIK: cpp
*/
#include <fstream.h>
#include <iostream.h>
#include <math.h>

const long int MAXN = 200000;
long int n, a[MAXN], b[MAXN];

char* infile = "reli.in";
char* outfile = "reli.out";

long int joe_100(long int left, long int right);

void save()
{	
	ofstream fout(outfile);
	
	fout << joe_100(1, n) << endl;

}

void load()
{
	ifstream fin(infile);

	fin >> n;

	for (long int i = 1; i <= n; i++) 
	{
		fin >> a[i];

	}

	a[n + 1] = n + 2;
}



long int joe_100(long int left, long int right)
{
	if (left == right) return 0;

	long int m = (left + right) / 2;

	long int flips = joe_100(left, m) + joe_100(m + 1, right);

	long int i = left;
	long int j = m + 1;
	long int k = left;
	long int sub = 0;

	while ((i <= m) && (j <= right))
	{
		if (a[i] < a[j])
		{
			b[k] = a[i];
			sub += abs(i - k);
			sub = sub % 100000;
			i++;
			k++;
		}
		else
		
		{
			b[k] = a[j];
			sub += abs(j - k);
			sub = sub % 100000;
			j++;
			k++;
		}
	}

	while (i <= m)
	{
		b[k] = a[i];
		sub += abs(i - k);
		sub = sub % 100000;
		i++;
		k++;
	}

	while (j <= right)
	{
		b[k] = a[j];
		sub += abs(j - k);
		sub = sub % 100000;
		j++;
		k++;
	}

	for (i = left; i <= right; i++) a[i] = b[i];
	
	flips += sub / 2;

	return (flips % 10000);
}


int main()
{
	load();
	save();
		
	return 0;
}