Masala #0659

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.

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\)

Bitta butun son - masalaning javobini chiqaring.