Mega İnversiyalar

Sıralama alqoritmində $n^2$ üst sərhədini əldə etmək asandır: sadəcə səhv sırada duran iki elementi tapıb onların yerlərini dəyişmək kifayətdir. Konrad isə alqoritmdə iki deyil, düzgün sırada olmayan üç elementi götürməyi planlaşdırdı. Yəni $i<j<k$ olan üç elementi $a_i>a_j>a_k$ şəklində götürək və onları $a_k,a_j,a_i$ sırasına düzək. Əgər ilkin alqoritmdə addımların sayını maksimum inversiya sayı $n\cdot (n-1)/2$ ilə məhdudlaşdırsaq, Konrad öz alqoritm versiyasında da dəyişdirilən üçlüklərin sayını bu dəyərlə məhdudlaşdırmaq istəyir. Belə üçlüklərin sayını hesablayan proqram yazın.

Giriş verilənləri

Birinci sətir ardıcıllığın uzunluğunu $n(1\le n\le 10^5)$ ehtiva edir.

Növbəti sətir $a_1,a_2,...,a_n(1\le a_i\le n)$ ədədlər ardıcıllığını ehtiva edir.

Çıxış verilənləri

İnversiya edilmiş üçlüklərin sayını çıxarın.

Nümunələr