Bitris

$2\ast N$ kubikdən ibarət bir dəst var. Hər bir kubikdə $1$-dən $N$-ə qədər olan bir natural ədəd yazılıb və hər bir ədəd dəqiq iki kubikdə təkrarlanır. Kubiklər bir sütunda düzülüb. Eyni ədədləri daşıyan iki kubik yan-yana gəldikdə, onlar yox olur: hər iki kubik məhv olur və onların üstündəki kubiklər aşağı düşür. Məqsəd sütunu tamamilə məhv etməkdir. Bunun üçün istənilən iki yan-yana duran kubikin yerini dəyişməyə icazə verilir. Yerdəyişmə yalnız mövcud vəziyyətdə mümkün olan bütün aniqilasiyalar başa çatdıqdan sonra edilə bilər.

Məsələn, əgər $N=4$ və kubiklər əvvəlcə belə düzülüb:

bir yerdəyişmə etmək lazımdır. $3$ işarəli kubiklər dərhal aniqilasiya olunur;

aşağıdan dördüncü kubik (işarəsi $1$ olan) və aşağıdan beşinci kubik (işarəsi $4$ olan) yerlərini dəyişdirək;

bundan sonra ardıcıl olaraq $4$, $1$ və $2$ işarəli kubiklər aniqilasiya olunur. Əlbəttə, aşağıdan üçüncü və dördüncü kubikləri də dəyişmək olar (bu halda $1$ və $4$ işarəli kubiklər eyni vaxtda aniqilasiya olunur və onlardan sonra $2$ işarəli kubiklər aniqilasiya olunur), ikinci və üçüncü də dəyişmək olar. Məqsəd, ən az mümkün yerdəyişmə edərək bütün kubikləri məhv etməkdir. Daha dəqiq, bunun üçün lazım olan ən az yerdəyişmə sayını tapmaqdır.

Giriş məlumatları

Proqram klaviaturadan natural ədəd $N$ ($2\le N\le 100000$) oxuyur, sonra isə aşağıdan yuxarıya doğru kubiklərin işarələri olan $2\ast N$ ədəd. Bütün ədədlər bir boşluqla ayrılıb.

Çıxış məlumatları

Proqram ekrana bir tam qeyri-mənfi ədəd $M$ çıxarır – bütün sütunu məhv etmək üçün lazım olan ən az yerdəyişmə sayı.

Nümunələr