Задача E2. Дипломы 2.0 ≡

Условие

Сегодня в ДВФУ состоится традиционное вручение дипломов выпускникам института математики и компьютерных наук. Каждый год это особенное событие и большой праздник, как для выпускников, так и для сотрудников факультета, своеобразное подведение итогов совместного многолетнего труда.

В этом году из института выпускается n студентов. Еще давным-давно, при поступлении, каждому студенты был выдан порядковый номер, который зависел от их места в конкурсном списке по результатам вступительных испытаний. Те, кто были выше в конкурсном списке, имели более низкий порядковый номер. То есть, если человек сдал вступительные лучше всех, то имел 1-й порядковый номер, кто сдал чуть хуже этого человека, но лучше всех остальных — 2-й, и так далее. Хоть это и было очень давно, эти номера закрепились за ними до конца их учебных дней.

В качестве введения новшества, институт решил распечатать конверты с этими порядковыми номерами и запаковать дипломы выпускников в принадлежащие их номеру конверты. Они сложили все конверты в стеклянный "бокс", расположив их слева направо по возрастанию. Бокс имел два отверстия для того, чтобы доставать дипломы: слева и справа.

Во время начала церемонии декану вручили список, по которому он должен выдавать дипломы. i-й по счету диплом должен быть выдан студенту под порядковым номером a_i. Так как укладывали все дипломы до получения этого списка, расположение их не такое, как должно быть. Они решили действовать по следующей тактике: вытаскивать дипломы по-очереди до того момента, пока не достанут нужный, и складывать все выложенные дипломы в том же порядке, как они и лежали. Т.е. если нужно достать диплом под номером 4, то сначала необходимо выложить дипломы 6 и 5 (или 1, 2 и 3, так как бокс имеет отверстия с двух сторон), а затем сложить их обратно в том же порядке. После того, как диплом выдан, он пропадает из бокса. На каждую операцию взятия и складывания дипломом затрачивается одно действие. Такая тактика, кстати, выбрана не просто так, они хотят ускорить выдачу дипломов и при этом не запутаться.

Вам дан список порядка выдачи дипломов. Определите, за какое наименьшее количество действий возможно выдать все дипломы, следуя данной тактике.

Формат входных данных

В первой строке входных данных записано натуральное число n — количество студентов.

Во второй строке записано n натуральных чисел a_i — порядок выдачи дипломов студентам по их порядковым номерам. Гарантируется, что каждое a_i уникальное.

Формат выходных данных

Выведите минимально возможное количество действий, за которое можно выдать все дипломы, следуя данной тактике.

Ограничения

1 ≤ n ≤ 2 ⋅ 10⁵

1 ≤ a_i ≤ n

Примеры тестов

6
4 3 5 2 1 6

18

2
2 1

2

5
1 2 3 4 5

5

6
5 3 6 2 4 1

14