Qatar qatarı çeşidləyicisi
На köhnə dəmiryolu stansiyasında siz hələ də son qalan "qatar çeşidləyicilərindən" biri ilə qarşılaşa bilərsiniz. Qatar çeşidləyicisi - dəmiryolu işçisidir və onun yeganə vəzifəsi qatar vaqonlarını yenidən düzəltməkdir. Vaqonlar düzgün qaydada yerləşdirildikdən sonra, qatar maşinistinin etməli olduğu tək şey, yükün nəzərdə tutulduğu stansiyalarda vaqonları bir-bir buraxmaqdır.
"Qatar çeşidləyicisi" adı, bu vəzifəni ilk dəfə yerinə yetirən şəxsdən gəlir, dəmiryolu körpüsünün yanında yerləşən stansiyada. Körpü şaquli açılmaq əvəzinə, çayın ortasındakı sütun ətrafında fırlanırdı. Körpünü 90 dərəcə döndərərək, qayıqlar sola və ya sağa keçə bilərdi.
İlk qatar çeşidləyicisi aşkar etdi ki, körpü üzərində maksimum iki vaqonla işləmək mümkündür. Körpünü 180 dərəcə döndərərək, vaqonlar yerlərini dəyişirdi, bu da ona vaqonları yenidən düzəltməyə imkan verirdi (yan təsir olaraq, vaqonlar sonra əks istiqamətə dönürdü, amma qatar vaqonları hər iki istiqamətdə hərəkət edə bilər, buna görə də bu heç kəsi narahat etmirdi).
İndi, demək olar ki, bütün dəmiryolu çeşidləyiciləri yoxa çıxdığı üçün, dəmiryolu şirkəti onların işini avtomatlaşdırmaq istəyir. Hazırlanmalı olan proqramın bir hissəsi, verilmiş qatar üçün vaqonları qaydaya salmaq üçün lazım olan ən az sayda iki qonşu vaqonun yerlərini dəyişmə əməliyyatını müəyyən edən prosedurdur. Sizin vəzifəniz belə bir proqram yaratmaqdır.
Giriş məlumatları
Birinci sətirdə testlərin sayı n verilir. Hər test iki sətirdən ibarətdir. Testin birinci sətiri qatarın uzunluğunu müəyyən edən tam ədəd l (0 ≤ l ≤ 10000) ehtiva edir. Testin ikinci sətiri vaqonların cari sırasını göstərən 1-dən l-ə qədər olan ədədlərin bir permutasiyasını ehtiva edir. Vaqonlar elə qaydada düzülməlidir ki, 1 nömrəli vaqon birinci, sonra 2 nömrəli vaqon və s. olsun. l nömrəli vaqon sonuncu olmalıdır.
Çıxış məlumatları
Hər test üçün "Optimal train swapping takes s swaps." cümləsini çıxarın, burada s tam ədəddir.