Недавно руководители Отеля поняли, что гостей становится все больше и нужно расширять штат. С чего бы начать? Первым на работу взяли нового Портье.
Но вот незадача, Портье ещё не успел освоиться на новом месте, как уже начались проблемы. Недовольные постояльцы вызвали его к себе в номер на шестом этаже, однако, по неопытности он заблудился и зашел в комнату \(404\)!!! А там…Лабиринт.
Лабиринт представляет собой последовательность из \(n\) дверей, расположенных друг за другом на одном этаже. Каждая \(i\)-я дверь покрашена в какой-то цвет \(a_i\), причём на этаже ровно по две двери каждого из цветов.
Допустим, что \(i\)-я и \(j\)-я двери покрашены в один и тот же цвет, причём \(i < j\). В таком случае, если Портье зайдёт в \(i\)-ю дверь, то он окажется между \(j\)-й и \((j+1)\) -й дверьми и сможет дальше зайти в одну из них. Если же он зайдёт в \(j\)-ю дверь, то он окажется между \((i-1)\) -й и \(i\)-й дверьми и далее сможет зайти в одну из них. Если \(i = 1\), то войдя в \(j\)-ю дверь, Портье окажется левее первой двери и далее сможет зайти только в неё же, а если \(j = n\), то войдя в \(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\)-й двери в последовательности. Гарантируется, что в лабиринте ровно по две двери каждого из цветов.
На единственной строке выведите минимальное количество проходов через двери, которое потребуется для того, чтобы выбраться из дверного лабиринта.
Ниже на картинке изображено пояснение к первому примеру из условия.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2 1 3 3 2
|
5
|
|
2
|
8
3 2 3 2 1 4 1 4
|
8
|