Ultra-sürətli sıralama#1303
Bu məsələ Siz müəyyən bir çeşidləmə alqoritmini təhlil etməlisiniz. Alqoritm uzunluğu olan fərqli tam ədədlərdən ibarət ardıcıllığı artan sıra ilə düzülənə qədər bir-biri ilə qonşu olan iki elementin yerlərini dəyişməklə emal edir. Məsələn, aşağıdakı giriş ardıcıllığı üçün
9 1 0 5 4
Ultra-QuickSort alqoritmi aşağıdakı çıxışı verir:
0 1 4 5 9
Sizin tapşırığınız, verilmiş giriş ardıcıllığının artan sıra ilə düzülməsi üçün tələb olunan ən az qonşu dəyişmələrin (swap) sayını müəyyən etməkdir.
Bir neçə test halından ibarətdir. Hər bir test halının birinci sətrində ardıcıllığın uzunluğu (n \leq 500\,000) verilir. Sonrakı sətrin hər birində (0 \leq a[i] \leq 999\,999\,999) — ardıcıllığın -ci elementi verilir. Sonuncu test halında n = 0 olur və bu hal emal edilməməlidir.
Hər bir giriş ardıcıllığı üçün bir sətrdə bir ədəd — ardıcıllığın artan sıra ilə düzülməsi üçün tələb olunan minimal qonşu dəyişmələrin sayını çap edin.
Nümunə 1