Sıralama#7770

Sıralama

1 saniyə

128 meqabayt

Çox asan

Ayjanın $n$ tam ədəddən ibarət $S_{0}, S_{1}, ..., S_{n - 1}$ S_0, S_1, ..., S_{n-1} ardıcıllığı var. Bu ardıcıllıq $0$ -dan $n - 1$ n - 1-ə qədər olan fərqli ədədlərdən ibarətdir. Ayjan onu artan sıraya görə çeşidləməyə çalışır, bəzi element cütlərini yerlərini dəyişməklə. Onun dostu Yermek də elementlərin yerlərini dəyişdirməyi planlaşdırır, lakin onun hərəkətlərinin faydalı olacağına heç bir zəmanət yoxdur.

Yermek və Ayjan ardıcıllığı mərhələ-mərhələ dəyişdirir. Hər mərhələdə əvvəlcə Yermek bir dəyişdirmə edir, sonra Ayjan öz dəyişdirməsini edir. Daha dəqiq desək, dəyişdirməni həyata keçirən iştirakçı iki icazəli mövqe seçir və həmin mövqelərdəki elementlərin yerlərini dəyişir. Qeyd edək ki, seçilmiş mövqelər mütləq fərqli olmamalıdır. Əgər onlar üst-üstə düşürsə, element özü ilə dəyişdirilir və ardıcıllıq dəyişməz qalır.

Ayjan bilir ki, Yermek $S$ ardıcıllığını çeşidləməyə çalışmır və onun seçəcəyi mövqeləri əvvəlcədən bilir. Yermek $m$ mərhələ həyata keçirməyi planlaşdırır. Mərhələlər $0$ -dan $m - 1$ m - 1-ə qədər nömrələnir. Hər $i$ üçün ( $0$ -dan $m - 1$ m - 1-ə qədər daxil olmaqla) Yermek $i$ nömrəli mərhələdə $x_{i}$ x_i və $y_{i}$ y_i mövqelərini seçir.

Ayjan $S$ ardıcıllığını çeşidləmək istəyir. Hər mərhələnin başlanğıcından əvvəl, əgər ardıcıllıq artıq artan sıraya görə çeşidlənibsə, proses dərhal dayanır. $S$ -in başlanğıc ardıcıllığı və Yermekin seçəcəyi mövqelər verilir. Ayjanın $S$ -i çeşidləmək üçün istifadə edə biləcəyi dəyişdirmələr ardıcıllığını tapmaq tələb olunur. Bəzi alt tapşırıqlarda mümkün qədər qısa dəyişdirmələr ardıcıllığını tapmaq lazımdır. $S$ ardıcıllığının $m$ və ya daha az mərhələdə çeşidlənə biləcəyi zəmanət verilir.

Əgər Yermekin dəyişdirməsindən sonra $S$ ardıcıllığı artıq çeşidlənibsə, Ayjan eyni mövqelərin dəyişdirilməsini seçə bilər (məsələn, $0$ və $0$ ). Onda ardıcıllıq mərhələnin sonuna qədər çeşidlənmiş qalacaq və məqsədə çatılacaq. Həmçinin qeyd edək ki, əgər $S$ ardıcıllığı əvvəlcədən çeşidlənibsə, mərhələlərin minimum sayı $0$ -a bərabərdir.

$S$ ardıcıllığı, mərhələlərin sayı $m$ və $X$ və $Y$ mövqe ardıcıllıqları verilir. Ayjanın $S$ ardıcıllığını çeşidləmək üçün istifadə edə biləcəyi dəyişdirmələr ardıcıllığını tapın.

Giriş

Birinci sətir $S$ ardıcıllığının uzunluğunu ehtiva edir.

İkinci sətir başlanğıc ardıcıllığı $S_{0}, S_{1}, ..., S_{n - 1} (n \leq 200000)$ S_0, S_1, ..., S_{n-1}~(n \le 200000) ehtiva edir.

Növbəti sətir Yermekin planlaşdırdığı mərhələlərin sayını $m (m \leq 3 \cdot n)$ m~(m \le 3 \cdot n) ehtiva edir.

Növbəti $m$ sətrin hər biri $x_{i}$ x_i və $y_{i}$ y_i ədədlərinin cütünü ehtiva edir. Onlar o deməkdir ki, $i$ mərhələsində $(0 \leq i \leq m - 1)$ (0 \le i \le m - 1) Yermek $x_{i}$ x_i və $y_{i}$ y_i mövqelərindəki elementləri dəyişdirməyi planlaşdırır.

Çıxış

Birinci sətirdə Ayjanın həyata keçirdiyi dəyişdirmələrin sayını $R$ çıxarın.

Növbəti $R$ sətirdə Ayjanın $S$ -i çeşidləmək üçün istifadə edə biləcəyi minimum uzunluqlu dəyişdirmələr ardıcıllığını çıxarın.

Hər sətirdə dəyişdirmə üçün $p_{i}$ p_i və $q_{i}$ q_i mövqe cütünü çıxarmaq lazımdır.

Nümunələr

Nümunə 1. Fərz edək ki:

Başlanğıc ardıcıllıq: $S = 4, 3, 2, 1, 0$ S = 4, 3, 2, 1, 0.
Yermek altı dəyişdirmə həyata keçirməyi planlaşdırır $(m = 6)$ (m = 6).
Yermekin seçəcəyi mövqeləri müəyyən edən $X$ və $Y$ ardıcıllıqları: $X = 0, 1, 2, 3, 0, 1$ X = 0, 1, 2, 3, 0, 1 və $Y = 1, 2, 3, 4, 1, 2$ Y = 1, 2, 3, 4, 1, 2. Yəni mövqe cütləri: $(0, 1), (1, 2), (2, 3), (3, 4), (0, 1)$ (0, 1), (1, 2), (2, 3), (3, 4), (0, 1) və $(1, 2)$ .

Bu halda Ayjan $S$ ardıcıllığını üç mərhələdə $0, 1, 2, 3, 4$ 0, 1, 2, 3, 4-ə çevirə bilər. Məsələn, $(0, 4), (1, 3)$ (0, 4), (1, 3) və sonra $(3, 4)$ cütlərini seçməklə. Aşağıdakı cədvəl Yermek və Ayjanın $S$ ardıcıllığını necə dəyişdirdiyini göstərir.

Nümunə 2. Fərz edək ki:

Başlanğıc ardıcıllıq: $S = 3, 0, 4, 2, 1$ S = 3, 0, 4, 2, 1.
Yermek beş dəyişdirmə həyata keçirməyi planlaşdırır $(m = 5)$ (m = 5).
Yermekin seçəcəyi mövqe cütləri: $(1, 1), (4, 0), (2, 3), (1, 4)$ (1, 1), (4, 0), (2, 3), (1, 4) və $(0, 4)$ .

Bu halda Ayjan $S$ ardıcıllığını üç mərhələdə çeşidləyə bilər, məsələn, $(1, 4), (4, 2)$ (1, 4), (4, 2) və sonra $(2, 2)$ cütlərini seçməklə. Aşağıdakı cədvəl Yermek və Ayjanın $S$ ardıcıllığını necə dəyişdirdiyini göstərir.

Nümunə 1

Nümunə 2