Manhetten Sıralaması
Başqa bir çeşidləmə problemi! Bu dəfə sizə N fərqli tam ədədlərdən ibarət S ardıcıllığı verilir və yalnız bir əməliyyatdan istifadə edərək onu minimum xərclə çeşidləmək tələb olunur:
Manhetten dəyişməsi!
S_i və S_j ardıcıllığın müvafiq olaraq i və j mövqelərindəki iki elementi olsun, S_i və S_j üzərində Manhetten dəyişmə əməliyyatını tətbiq etmək, hər iki elementi |i-j| xərci ilə dəyişdirir. Məsələn, {9, 5, 3} ardıcıllığı verildikdə, ardıcıllığı bir Manhetten dəyişmə əməliyyatı ilə birinci və sonuncu elementləri dəyişdirərək ümumi 2 xərci ilə (mövqelərin mütləq fərqi 9 və 3) çeşidləyə bilərik.
Giriş verilənləri
Girişin ilk sətri test halların sayı olan T tam ədədini ehtiva edir. Hər bir test halı 2 sətirdən ibarətdir. Birinci sətir ardıcıllığın uzunluğu olan tək tam ədəd (1 ≤ N ≤ 30) S-ni ehtiva edir. İkinci sətir S elementlərini təmsil edən N boşluqla ayrılmış tam ədədləri ehtiva edir. Bütün ardıcıllıq elementləri fərqlidir və 32 bit imzalı tam ədədə sığır.
Çıxış verilənləri
Hər bir test halı üçün yalnız bir tam ədəd olan bir sətir çıxarın, yalnız Manhetten dəyişmə əməliyyatından istifadə edərək ardıcıllığı çeşidləməyin minimum xərci.