Sıralama
Aycanın n tam ədəddən ibarət S[0], S[1], ..., S[n-1] ardıcıllığı var. Bu ardıcıllıq 0-dan n - 1-ə qədər müxtəlif ədədlərdən ibarətdir. Aycan bu ardıcıllığı artan sıraya düzəltmək istəyir, bəzi element cütlərini yerlərini dəyişdirərək. Onun dostu Ermek də bəzi element cütlərini dəyişdirməyə hazırlaşır, lakin onun bunu faydalı şəkildə edəcəyinə əminlik yoxdur.
Ermek və Aycan ardıcıllığı bir neçə mərhələdə dəyişdirməyə hazırlaşırlar. Hər mərhələdə əvvəlcə Ermek elementlərin yerlərini dəyişdirir, sonra Aycan başqa bir dəyişiklik edir. Dəyişiklik edən şəxs iki düzgün mövqe seçir və həmin mövqelərdəki elementlərin yerlərini dəyişdirir. Qeyd edək ki, iki mövqe mütləq fərqli olmamalıdır. Onlar bərabər olduqda, element öz-özü ilə dəyişdirilir. Belə bir hərəkət ardıcıllığı dəyişdirmir.
Aycan bilir ki, Ermek ardıcıllığı S sıralamaq barədə narahat deyil. O, Ermekin hansı mövqeləri seçəcəyini bilir. Ermek m mərhələdə iştirak etməyi planlaşdırır. Mərhələlər 0-dan m - 1-ə qədər nömrələnir. Bütün i üçün 0-dan m - 1-ə qədər daxil olmaqla, Ermek i nömrəli mərhələdə x[i] və y[i] mövqelərini seçəcək.
Aycan ardıcıllığı S sıralamaq istəyir. Hər mərhələnin əvvəlində, əgər Aycan görsə ki, ardıcıllıq artıq artan sıradadır, bütün proses dayandırılır. Başlanğıc ardıcıllığı S və Ermekin seçəcəyi mövqelər verilir, Aycanın ardıcıllığı sıralamaq üçün istifadə edə biləcəyi dəyişikliklər ardıcıllığını tapmaq tələb olunur. Bəzi alt məsələlərdə mümkün qədər qısa dəyişikliklər ardıcıllığını tapmaq tələb olunur. Məlumdur ki, ardıcıllığı S m və ya daha az mərhələdə sıralamaq mümkündür.
Əgər Aycan görsə ki, Ermekin etdiyi dəyişiklikdən sonra ardıcıllıq S sıralanıb, o, bərabər mövqelərdə dəyişiklik seçə bilər (məsələn 0 və 0). Nəticədə ardıcıllıq S mərhələnin sonunda sıralanmış olaraq qalacaq və Aycan məqsədinə çatacaq. Həmçinin qeyd edək ki, əgər başlanğıcda ardıcıllıq S sıralanıbsa, sıralamaq üçün lazım olan minimum mərhələ sayı 0-dır.
Ardıcıllıq S, dəyişikliklərin sayı m və mövqelərin ardıcıllığı X və Y verilir. Aycanın ardıcıllığı sıralamaq üçün istifadə edə biləcəyi dəyişikliklər ardıcıllığını tapın.
Nümunə 1
Tutaq ki:
Başlanğıc ardıcıllıq: S = 4, 3, 2, 1, 0.
Ermek altı dəyişiklik etməyi planlaşdırır (m = 6).
Ermekin seçəcəyi mövqeləri təsvir edən X və Y ardıcıllıqları belədir: X = 0, 1, 2, 3, 0, 1 və Y = 1, 2, 3, 4, 1, 2. Yəni, Ermekin seçməyi planlaşdırdığı mövqe cütləri (0, 1), (1, 2), (2, 3), (3, 4), (0, 1) və (1, 2) olacaq.
Bu halda Aycan ardıcıllığı 0, 1, 2, 3, 4 şəklinə üç mərhələdə çevirə bilər. O, bunu (0, 4), (1, 3) və sonra (3, 4) mövqelərini seçərək edə bilər. Aşağıdakı cədvəl Ermek və Aycanın ardıcıllığı S necə dəyişdirdiyini əks etdirir.
Nümunə 2
Tutaq ki:
Başlanğıc ardıcıllıq: S = 3, 0, 4, 2, 1.
Ermek beş dəyişiklik etməyi planlaşdırır (m = 5).
Ermekin seçməyi planlaşdırdığı mövqe cütləri: (1, 1), (4, 0), (2, 3), (1, 4) və (0, 4).
Bu halda Aycan ardıcıllığı S üç mərhələdə sıralaya bilər, məsələn, (1, 4), (4, 2) və sonra (2, 2) mövqelərini seçərək. Aşağıdakı cədvəl Ermek və Aycanın ardıcıllığı S necə dəyişdirdiyini əks etdirir.
Giriş məlumatları
Birinci sətir ardıcıllığın uzunluğunu S ehtiva edir. İkinci sətir başlanğıc ardıcıllığı S[0], S[1], ..., S[n-1] (n ≤ 200000) ehtiva edir. Növbəti sətir Ermekin planlaşdırdığı dəyişikliklərin sayını m (m ≤ 3 * n) ehtiva edir. Növbəti m sətirin hər biri x[i] və y[i] cütünü ehtiva edir. Onlar i-ci (0 ≤ i ≤ m - 1) mərhələdə Ermekin x[i] və y[i] mövqelərindəki elementləri dəyişdirməyi planlaşdırdığını göstərir.
Çıxış məlumatları
Birinci sətirdə Aycanın dəyişikliklərinin sayını R çıxarın. Növbəti R sətirdə Aycanın ardıcıllığı sıralamaq üçün istifadə edə biləcəyi minimal uzunluqda dəyişikliklər ardıcıllığını çıxarın. Hər sətirdə dəyişiklik üçün mövqe cütünü p[i] və q[i] çıxarın.