Ay görüşləri çox sevir#10659
Luna maraqlı bir fikir tapdı. O, dostunu sıraya düzdü və hər birinə -dən -ə qədər tam ədəd verdi. Hər bir ədəd dəqiq iki dəfə təkrarlanır. Eyni ədədi olan hər bir dost cütlük təşkil edir.
Luna hər bir cütlüyü görüşə göndərmək istəyir. Lakin bu o qədər də asan deyil. Bir cütlüyü görüşə göndərmək üçün, cütlüyü təşkil edən iki dost sırada bir-birinin yanında durmalıdır, yəni onların arasında başqa heç kim olmamalıdır.
Lunanın edə biləcəyi iki mümkün əməliyyat var:
O, sırada bir-birinin yanında duran istənilən iki dostun yerlərini dəyişə bilər.
Əgər cütlük sırada bir-birinin yanında durursa, Luna onları görüşə göndərə bilər. Bu, cütlüyü sıradan çıxarır. Sonra qalan dostlar boş yerləri doldurur.
Əməliyyatlar istənilən ardıcıllıqla yerinə yetirilə bilər. Məsələn, o, dostların yerlərini dəyişə bilər, sonra bir neçə dost cütlüyünü görüşə göndərə bilər və sonra yenidən yerlərini dəyişə bilər.
Bütün dostları görüşə göndərmək üçün lazım olan minimum əməliyyat sayını tapın və çıxarın.
Birinci sətir bir tam ədəd ehtiva edir.
İkinci sətir tam ədəd a_i (1 \leq a_i \leq n) ehtiva edir — dostların ədədlərinin eyni ardıcıllığı.
Lunanın bütün cütlükləri görüşə göndərməsi üçün lazım olan əməliyyatların minimum sayını çıxarın.
Nümunə 1
Nümunə 2
Birinci nümunədə Luna üçüncü və dördüncü dostun yerlərini dəyişə bilər. Bundan sonra sıra belə görünəcək: 3 1 1 2 2 3.
Sonra o, 1 nömrəli cütlüyü və 2 nömrəli cütlüyü (istənilən ardıcıllıqla) görüşə göndərə bilər. Bunu etdikdən sonra, 3 nömrəli iki dost artıq sırada bir-birinin yanında olacaq və Luna onları da görüşə göndərə bilər.
Ümumilikdə bu həll 4 əməliyyat yerinə yetirir: bir dəfə yerlərini dəyişmək və üç dəfə görüşə göndərmək.
Blok 1 (7 xal): Hər bir cütlük arasında başqa heç kim yoxdur və həmçinin 1 \le n \le 100.
Blok 2 (8 xal): Hər bir cütlük arasında maksimum bir nəfər var və həmçinin 1 \le n \le 100.
Blok 3 (11 xal): Sıradakı ilk dost -dən -ə qədər ədədləri dəqiq bir dəfə alıb, lakin mütləq sıralanmış qaydada deyil. Üstəlik, 1 \le n \le 3\,000.
Blok 4 (16 xal): Sıradakı ilk dost -dən -ə qədər ədədləri dəqiq bir dəfə alıb, lakin mütləq sıralanmış qaydada deyil. Üstəlik, 1 \le n \le 500\,000.
Blok 5 (22 xal): 1 \le n \le 3\,000.
Blok 6 (36 xal): 1 \le n \le 500\,000.