Козак Вус i секрет Ледi
Козак Вус i секрет Ледi
У кожного є свої секрети. Ледi пообiцяла розповiсти свiй Новий Надсекретний Секрет (ННС) Козаковi Вусу на день народження, але не стримала слово. Натомiсть вона придумала гру для Козака.
Є колода з 2n карт, в якiй кожна карта номiналом вiд 1 до n зустрiчається рiвно двiчi. Козак вус робить 2n крокiв. На кожному кроцi вiн вибирає верхню карту або наступну пiсля неї та витягує її з колоди. Коли вiн витягує двi карти з однаковим номiналом поспiль, то вiн отримує один бал.
Якщо Козак Вус набере найбiльшу можливу кiлькiсть балiв, то Ледi, можливо, розповiсть йому ННС. Допоможiть Козаковi дiзнатися ННС i напишiть програму, яка знаходить максимальну кiлькiсть балiв, яку можна набрати.
Формат вхiдних даних
Перший рядок мiстить одне цiле число n (**1 ≤ n ≤ 100 000**) — максимальний номiнал карт.
Другий рядок мiстить 2n цiлих чисел a1
, a2
, . . . , a2n
(**1 ≤ ai
≤ n**) — номiнал i-ої карти зверху колоди. Гарантується, що кожне число вiд 1 до n зустрiчається рiвно двiчi.
Формат вихiдних даних
В єдиному рядку виведiть одне число — вiдповiдь на задачу
Примiтка
У першому прикладi можна витягувати карти у такому порядку: [1, 1, 2, 2, 3, 3].
У другому прикладi можна витягувати карти у такому порядку: [4, 2, 5, 6, 2, 7, 7, 1, 1, 4, 6, 3, 3, 5].
3 1 1 3 2 2 3
3
7 1 4 2 5 6 2 7 7 1 3 4 6 3 5
3