Con Jon İnversiyaları
John yaxınlarda inversiyanın aşağıdakı tərifinə rast gəldi.
İnversiya, s[k] ədədlər ardıcıllığında, elə bir s[i], s[j] cütüdür ki, i < j və s[i] > s[j].
John hesab edir ki, inversiyalar ədədlər ardıcıllığının nə dərəcədə yaxşı sıralandığını qiymətləndirmək üçün ideal vasitədir. Ardıcıllıqda nə qədər az inversiya varsa, o qədər yaxşı sıralanmışdır. Məsələn, əgər ardıcıllıq artan qaydada sıralanıbsa, o zaman sıfır inversiya ehtiva edir.
Petr John-a n kartdan ibarət bir dəst verdi. Hər kartda iki rəqəm yazılıb - biri qırmızı rəngdə, digəri isə mavi rəngdə. John bu kart dəstindən istifadə edərək inversiyalar haqqında biliklərini yoxlamaq istəyir.
O, kartları qarşısına təsadüfi qaydada qoyur və qarşısında yerləşən ədədlər ardıcıllığı üçün ümumi yaxşı inversiyalar sayını hesablayır. John inversiyanı yaxşı hesab edir, əgər o, eyni rəngli nömrələrdən ibarətdirsə. Bizim halda, yaxşı inversiya ya iki mavi, ya da iki qırmızı rəqəmdən ibarət ola bilər. Əgər John-un meyarlarına görə yaxşı inversiyaların sayı çoxdursa, o, kartları qarışdırır və prosesi təkrar edir.
Sizə John-a təsvir olunan alqoritmə uyğun olaraq mümkün olan ən az yaxşı inversiya sayını tapmağa kömək etmək tapşırılıb.
Giriş məlumatları
Birinci sətir kartların sayı n (1 ≤ n ≤ 100000) olan dəsti ehtiva edir. Növbəti n sətirdən hər biri bir kartı təsvir edir. i-ci sətir i-ci kartda qırmızı və mavi rəngdə yazılmış iki tam ədəd r[i] və b[i] (1 ≤ r[i], b[i] ≤ 10^9) ehtiva edir.
Çıxış məlumatları
Mümkün olan ən az yaxşı inversiya sayını çıxış edin.