Masala #0661

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 16 %
4.0 (Baholar 4)
14

  

O’chirish #4

Uzunligi 2n2n bo’lgan aa massiv berilgan. Massiv elementlari [1..n][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]a[i] va a[i+1](1i<n)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][1, 2, 2, 3, 1, 3] massivdan ikkita yonma-yon 2 lar o’chirib tashlanganindan so’ng massiv [1,3,1,3][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 nn kiritiladi (1n105)(1 ≤ n ≤ 10^5). Keyingi qatorda 2n2n ta butun son - massiv elementlari a1,a2,...,ana_1, a_2, ..., a_n kiritiladi (1ain)(1 ≤ a_i ≤ n).
 

1-subtask (7 ball): Bir xil qiymatli sonlar massivda yonma-yon joylashgan (1n105)(1 ≤ n ≤ 10^5).
2-subtask (8 ball): Bir xil qiymatli sonlar o’rtasida ko’pi bilan bitta boshqa son bor (1n100)(1 ≤ n ≤ 100).
3-subtask (11 ball): Massivning dastlabki nn ta elementi 1,2,3,...,n1, 2, 3,...,n sonlardan iborat, ammo sonlar o’rni ixtiyoriy bo’lishi mumkin (1n1000)(1 ≤ n ≤ 1000).
4-subtask (16 ball): Massivning dastlabki nn ta elementi 1,2,3,...,n1, 2, 3,...,n sonlardan iborat, ammo sonlar o’rni ixtiyoriy bo’lishi mumkin (1n105)(1 ≤ n ≤ 10^5).
5-subtask (22 ball): 1n10001 ≤ n ≤ 1000
6-subtask (36 ball): 1n1051 ≤ 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 - []

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin