Masala #0658

Xotira 16 MB Vaqt 1000 ms
14

O’chirish #1

Uzunligi \(2n\) bo’lgan \(a\) massiv berilgan. Massiv elementlari \([1..n]\) oralig’ida bo’lib, har bir qiymat massivda aniq 2 martadan uchraydi(ya’ni 1 ikki marta, 2 ikki marta, ..., n ikki marta). Massiv ustida quyidagi ikki amallarni bajarish mumkin:

- Massivning ikki qo’shni elementini (\(a[i]\) va \(a[i + 1] (1 ≤ i < n)\)) o’rnini almashtirish
- Massivdagi ikkita bir xil qiymatli qo’shni elementlarni o’chirib tashlash. Masalan \([1, 2, 2, 3, 1, 3]\) massivdan ikkita yonma-yon 2 lar o’chirib tashlanganindan so’ng massiv \([1, 3, 1, 3]\) ko’rinishga keladi.

Yuqoridagi amallarni ixtiyoriy tartibda bajarish mumkin bo’lsa, massivdagi barcha elementlarni o’chirib tashlash uchun kerak bo’ladigan minimal amallar sonini chiqaring.


Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son \(n\) kiritiladi \((1 ≤ n ≤ 10^5)\). Keyingi qatorda \(2n\) ta butun son - massiv elementlari \(a_1, a_2, ..., a_n\) kiritiladi \((1 ≤ a_i ≤ n)\).
 

1-subtask (7 ball): Bir xil qiymatli sonlar massivda yonma-yon joylashgan \((1 ≤ n ≤ 10^5)\).
2-subtask (8 ball): Bir xil qiymatli sonlar o’rtasida ko’pi bilan bitta boshqa son bor \((1 ≤ n ≤ 100)\).
3-subtask (11 ball): Massivning dastlabki \(n\) ta elementi \(1, 2, 3,...,n\) sonlardan iborat, ammo sonlar o’rni ixtiyoriy bo’lishi mumkin \((1 ≤ n ≤ 1000)\).
4-subtask (16 ball): Massivning dastlabki \(n\) ta elementi \(1, 2, 3,...,n\) sonlardan iborat, ammo sonlar o’rni ixtiyoriy bo’lishi mumkin \((1 ≤ n ≤ 10^5)\).
5-subtask (22 ball): \(1 ≤ n ≤ 1000\)
6-subtask (36 ball): \(1 ≤ n ≤ 10^5\)


Chiquvchi ma'lumotlar:

Bitta butun son - masalaning javobini chiqaring.


Misollar
# input.txt output.txt
1
3
3 1 2 1 2 3
4
Izoh:

Birinchi misolda, quyidagicha 4 ta amal bajarish mumkin:

1) 3- va 4- o’rindagi elementlarni o’rnini almashtiramiz, massiv [3, 1, 1, 2, 2, 3] ko’rinishda.
2) 1 qiymatli elementlarni o’chirib tashlaymiz - [3, 2, 2, 3]
3) 2 qiymatli elementlarni o’chirib tashlaymiz - [3, 3]
4) Vanihoyat, 3 qiymatli elementlarni o’chirib tashlaymiz - []