svetlanaastahov

09.08.2022 04:45

Информатика

Есть ответ 👍

Во время каникул в Санкт-Петербурге Арина посетила выставку художников-импрессионистов. Для полноты восприятия она взяла аудиогид, чтобы не просто рассматривать картины, но и узнавать что-то новое. Выставка представляет собой галерею из n картин, развешанных (по порядку, от первой к n -й) на одной стене музея. Арина хотела один раз пройтись по галерее, от картины с номером 1 1 до картины с номером n , но в её планы вмешались другие любители живописи, стоявшие у некоторых картин. Поэтому, если у картины уже стоял посетитель, Арина пропускала её и шла дальше. Дойдя до конца галереи, она развернулась и продолжила осмотр, пользуясь той же тактикой относительно остальных посетителей, но в этот раз останавливаться только у ещё не просмотренных картин. Таким образом ей пришлось несколько раз пройти от одного конца галереи до другого. Посмотрев последнюю картину Арина продолжила движение в том же направлении и вышла из музея. После культурной прогулки Арина решила посчитать сколько же раз она по галерее. На её удачу в памяти аудиогида сохранилась последовательность треков с номерами картин Арине — по последовательности номеров картин определите, какое минимальное количество раз она вдоль галереи. Входные данные В первой строке содержится целое число n (1≤≤105) ( 1 ≤ n ≤ 10 5 ) — количество картин в галерее. Во второй строке содержится n целых чисел a i (1≤≤) ( 1 ≤ a i ≤ n ) — номера картин в порядке их просмотра по истории аудиогида. Гарантируется, что ≠ a i ≠ a j , если ≠ i ≠ j . Выходные данные Выведите единственное целое число — минимально возможное количество раз, которое Арина вдоль галереи решить ,