407259: GYM102739 A Выставка импрессионистов

A. Выставка импрессионистовограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Во время каникул в Санкт-Петербурге Арина посетила выставку художников-импрессионистов. Для полноты восприятия она взяла аудиогид, чтобы не просто рассматривать картины, но и узнавать что-то новое.

Выставка представляет собой галерею из $$$n$$$ картин, развешанных (по порядку, от первой к $$$n$$$-й) на одной стене музея.

Арина хотела один раз пройтись по галерее, от картины с номером $$$1$$$ до картины с номером $$$n$$$, но в её планы вмешались другие любители живописи, стоявшие у некоторых картин. Поэтому, если у картины уже стоял посетитель, Арина пропускала её и шла дальше. Дойдя до конца галереи, она развернулась и продолжила осмотр, пользуясь той же тактикой относительно остальных посетителей, но в этот раз останавливаться только у ещё не просмотренных картин. Таким образом ей пришлось несколько раз пройти от одного конца галереи до другого. Посмотрев последнюю картину Арина продолжила движение в том же направлении и вышла из музея.

После культурной прогулки Арина решила посчитать сколько же раз она прошла по галерее. На её удачу в памяти аудиогида сохранилась последовательность треков с номерами картин.

Помогите Арине — по последовательности номеров картин определите, какое минимальное количество раз она прошла вдоль галереи.

Входные данные

В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество картин в галерее.

Во второй строке содержится $$$n$$$ целых чисел $$$a_i$$$ $$$(1 \le a_i \le n)$$$ — номера картин в порядке их просмотра по истории аудиогида. Гарантируется, что $$$a_i \not= a_j$$$, если $$$i \not= j$$$.

Выходные данные

Выведите единственное целое число — минимально возможное количество раз, которое Арина прошла вдоль галереи.

Система оценки

$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 10 & n \le 10 &\text { подзадача } & \\ \hline 2 & 30 & n \le 1000 & \text { подзадача } & 1 \\ \hline 3 & 30 & n \le 50 000 & \text { подзадача } & 1, 2 \\ \hline 4 & 30 & \text{ Без дополнительных ограничений } & \text { подзадача } & 1, 2, 3 \\ \hline \end{array}$$$$$$

ПримерВходные данные

8
3 5 7 1 6 4 8 2

Выходные данные

6

Примечание

Поясним приведённый пример.

Сначала Арина движется по направлению «от первой картины к последней» и смотрит картины 3, 5, 7.

Дойдя до конца аллеи, она поворачивает и возвращается назад, чтобы посмотреть на 1 картину.

Снова повернув, она отправляется смотреть на 6 картину.

Ещё один поворот — и она приходит к 4 картине.

Затем ей приходится повернуть ещё один раз, чтобы дойти до 8 картины.

После этого необходимо вернуться к картине номер 2.