U zemlji Bajtoviji se, tradicionalno, svake prestupne godine održava egzibiciona reli trka. Vozači i ekipe se okupljaju u Donjem Bitu, gde izlažu svoje automobile zainteresovanoj publici. Zatim svaki vozač dobija startni broj i trka počinje. Vozači kreću ka Gornjem Bitu prema startnim brojevima u razmacima od po 3 minuta. Po završetku trke, u Gornjem Bitu se održava veliko slavlje nakon koga publika i učesnici kolektivno peru sudove. Tek nakon što su sudovi oprani, proglašava se pobednik trke. Legenda kaže da će zavladati glad do sledećeg relija, ako se pobednik proglasi uz prljave sudove.

I tako, od pamtiveka...

Uz savremeno doba dođoše i savremena shvatanja. Ministarstvo Saobraćaja, Automobilizma i Turizma, smatra da su trke suviše opasne i želi da ih zabrani uz obrazloženje da raspon od 3 minuta ostavlja veoma male manevarske mogućnosti i dovodi do neverovatno velikog broja jako rizičnih preticanja. Ako bi se interval povećao na bezbednih 7 minuta, trke bi trajale do kasno u noć kada više niko ne bi ostao da pere sudove. Potrebno je uveriti predstavnike Ministarstva da i pored raspona od 3 minuta ne dolazi do prevelikog broja preticanja.

Poznati su vam podaci vezani za poslednju održanu trku, preciznije: broj učesnika N (1 ≤ N ≤ 100000) i redosled kojim su takmičari stizali u Gornji Bit. Od vas se očekuje da odredite minimalan broj preticanja koji se mogao dogoditi na datoj trci.

Napomena:

Automobili takmičara su obeleženi startnim brojevima od 1 do N, i tim redom kreću sa starta. U prilog trci ide i podatak da u svakom preticanju učestvuju samo dva vozača. Još se nije desilo da neko od takmičara ne završi trku!

Ulaz:

U prvoj liniji tekstualnog fajla reli.in se nalazi broj vozača N. U svakoj od sledećih N linija se nalazi po jedan broj, i to u i+1-oj liniji, startni broj vozača koji je i-ti stigao u Gornji Bit.

Izlaz:

U prvoj i jedinoj liniji tekstualnog fajla reli.out potrebno je ispisati ostatak minimalnog broja preticanja pri deljenju sa 10000.

Primer:

5
4
3
2
1
5

6

Očigledno je da se u zadatku trazi broj zamena mesta susednih elemenata potrebnih za sortiranje datog niza.

Trivijalno resenje koristi BubbleSort algoritam i time simulira ceo proces. Vremenska slozenost ovakvog resenja je O(n²) i ono donosi oko 20% poena.

Jedno od efikasnijih resenja koristi modifikaciju MergeSort algoritma. MergeSort radi tako to niz podeli na dva podniza približno jednakih dužina, sortira levi i desni podniz a zatim elemente podnizova raspoređuje tako da se dobije sortiran niz. Pod pretpostavkom da su podnizovi sortirani, MergeSort bira manji od čeonih elemenata dva podniza, stavlja ga na kraj novog niza i uklanja iz odgovarajućeg podniza. Funkcija se izvrsava sve dok u bar jednom podnizu ima elemenata. Niz dobijen ovim postupkom je sortiran, čime je zadovoljena pretpostavka. Broj zamena potrebnih za sortiranje niza jednak je zbiru broja zamena potrebnih za sortiranje dva podniza i broja zamena potrebnih za raspoređivanje elemenata. Kako se raspoređivanje vrši linearno, dokazuje se da je vremenska složenost ovakvog algoritma O(n lg n).

/*
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;
}

#include <iostream>
#include <vector>

using namespace std;

long Count(vector<long> &A){

  if (A.size() <= 1)
    return 0;

  vector<long> A1, A2;

  for (long i=0;i<A.size()/2;i++)
    A1.push_back(A[i]);
  for (long i=A.size()/2;i<A.size();i++)
    A2.push_back(A[i]);

  long m = 0, c = Count(A1) + Count(A2);
  
  A.clear();
  for (long i=0;i<A1.size();i++) {
    for (;(m<A2.size())&&(A2[m]<A1[i]);m++) {
      A.push_back(A2[m]);
      c+= A1.size()-i;
    }
    A.push_back(A1[i]);
  }

  for (;m<A2.size();m++)
    A.push_back(A2[m]);

  return c;
}

int main(){
  
  long N, tmp;

  cin >> N;
  vector<long> A(N);

  for (long i=0;i<N;i++)
    cin >> A[i];

  cout << Count(A);
}