Laiko ribojimas: 1s

Atminties ribojimas: 32MB

Duomenų failas: issibarste_skaiciai.in

Rezultatų failas: issibarste_skaiciai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Išsibarstę skaičiai

Nedas, atėjęs į eilinį ŠIOM užsiėmimą, labai nustebo - klasė, kurioje paprastai vyksta pamokos, buvo tuščia! Be to, ant lentos buvo užrašyti skaičiai 2, 3, 8, 6, 1, šalia jų didelėmis raidėmis parašytas ir apibrauktas skaičius 5, lentos apačioje tekstas O KAS JEI N???, o lentos viršuje tekstas \\text{netvarka}=|\{(i,j):i<j,a[i]>a[j]}|.

Matyt mokytojas iš proto išėjo... - pagalvojo Nedas. Nepaisant tokių minčių, paslaptingi skaičiai ir užrašai pasirodė įdomūs ir Nedas norom nenorom pradėjo mąstyti apie jų prasmę. Ilgai galvojęs ir išnagrinėjęs lentoje parašytus skaičius, jis pagaliau pradėjo nujausti keistųjų užrašų prasmę ir suprasti, kas taip sutrikdė mokytoją. Nedo galvoje uždavinys atrodė ne toks jau ir sudėtingas: jei turime masyvą su skaičiais, tai "netvarka" yra kiekis tokių porų skaičių, kad pirmas eitų anksčiau, bet būtų didesnis už antrąjį.

Pavyzdžiui, ant lentos užrašytus skaičius 2, 3, 8, 6, 1 galime laikyti masyvu. Jame egzistuoja 5 poros skaičių, sudarančių masyvo netvarką (tokios poros yra (2,1), (3,1), (8,6), (8,1), (6,1)).

Pff, tiesiog patikrinsiu visas poras skaičių ir suskaičiuosiu, ne taip čia ir sun... - pagalvojo Nedas, bet jo mintis nutraukė į klasę įbėgęs mokytojas. Po pokalbio su juo, paaiškėjo, kad masyvas gali būti toks didelis, kad patikrinti visų porų per pakankamai trumpą laiką neišeis. Teks sugalvoti kažką efektyvesnio...

Pradiniai duomenys

Pirmoje eilutėje duotas vienas skaičius N - masyvo dydis (1\\leqN\\leq2\\cdotp10^5).

Antroje eilutėje duota N tarpais atskirtų sveikųjų skaičių a_i (1\\leqa_i\\leq10^9). Tai - masyvo elementai. Garantuota, kad visi masyvo elementai yra skirtingi.

Rezultatai

Pirmoje ir vienintelėje eilutėje jūsų programa turi išvesti vieną sveikąjį skaičių - duotojo masyvo netvarką.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5
2 3 8 6 1
 
5
 
3
3 1 2
 
2

Paaiškinimas

Pirmasis pavyzdys atitinką sąlygoje aprašytą atvejį.

Antrajame pavyzdyje poros, sudarančios netvarką, yra (3,1) ir (3,2).