Недавно руководители Отеля поняли, что гостей становится все больше и нужно расширять штат. С чего бы начать? Первым на работу взяли нового Портье.
Но вот незадача, Портье ещё не успел освоиться на новом месте, как уже начались проблемы. Недовольные постояльцы вызвали его к себе в номер на шестом этаже, однако, по неопытности он заблудился и зашел в комнату $$$404$$$!!! А там... Лабиринт.
Лабиринт представляет собой последовательность из $$$n$$$ дверей, расположенных друг за другом на одном этаже. Каждая $$$i$$$-я дверь покрашена в какой-то цвет $$$a_i$$$, причём на этаже ровно по две двери каждого из цветов.
Допустим, что две разные двери $$$i$$$ и $$$j$$$ покрашены в один и тот же цвет. В таком случае, если Портье зайдёт в $$$i$$$-ю дверь слева, то он окажется между $$$j$$$-й и $$$(j+1)$$$ -й дверьми и сможет дальше зайти в одну из них. Если же он зайдёт в $$$i$$$-ю дверь справа, то он окажется между $$$j$$$ -й и $$$(j - 1)$$$-й дверьми и далее сможет зайти в одну из них. Если $$$j = n$$$, то войдя в $$$i$$$-ю дверь слева, он окажется правее последней двери и выберется из лабиринта. Если же $$$j = 1$$$, то зайдя в $$$i$$$-тую дверь справа он окажется между первой дверью и началом лабиринта и сможет зайти только в первую дверь.
Изначально Портье находится левее первой двери и очень спешит выбраться. Пожалуйста, помогите ему найти минимальное количество проходов через двери для выхода из лабиринта.
В первой строке находится чётное число $$$n$$$ $$$(2 \le n \le 200\,000)$$$ — количество дверей в лабиринте.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), где $$$a_i$$$ — цвет $$$i$$$-й двери в последовательности. Гарантируется, что в лабиринте ровно по две двери каждого из цветов.
На единственной строке выведите минимальное количество проходов через двери, которое потребуется для того, чтобы выбраться из дверного лабиринта.
6 1 2 1 3 3 2
5
8 3 2 3 2 1 4 1 4
8
Ниже на картинке изображено пояснение к первому примеру из условия.
