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

У Yeri есть массив из $$$n + 2$$$ неотрицательных целых чисел: $$$a_0, a_1, ..., a_n, a_{n + 1}$$$.

Мы знаем, что $$$a_0 = a_{n + 1} = 0$$$.

Она хочет сделать все элементы $$$a$$$ равными нулю за минимальное количество операций.

За одну операцию она может сделать одно из следующих действий:

  • Выбрать самый левый максимальный элемент и изменить его на максимальный из элементов слева от него.
  • Выбрать самый правый максимальный элемент и изменить его на максимальный из элементов справа от него.

Помогите ей найти минимальное количество операций, необходимых для того, чтобы все элементы $$$a$$$ стали равны нулю.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).

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

Выведите одно целое число  — минимальное количество операций, необходимых для того, чтобы все элементы $$$a$$$ стали равны нулю.

Примеры
Входные данные
6
1 4 2 4 0 2
Выходные данные
7
Входные данные
5
1 3 5 4 2
Выходные данные
9
Входные данные
4
0 0 0 0
Выходные данные
0
Примечание

В первом примере вы получите $$$\langle 1, \underline{1}, 2, 4, 0, 2 \rangle$$$ при выполнении первой операции и $$$\langle 1, 4, 2, \underline{2}, 0, 2 \rangle$$$ при выполнении второй операции.

Один из способов достижения нашей цели показан ниже. (Подчеркивания показывают последнее изменение). $$$\langle 1, 4, 2, 4, 0, 2 \rangle \to \langle 1, 4, 2, \underline{2}, 0, 2 \rangle \to \langle 1, \underline{1}, 2, 2, 0, 2 \rangle \to \langle 1, 1, 2, 2, 0, \underline{0} \rangle \to \langle 1, 1, 2, \underline{0}, 0, 0 \rangle \to \langle 1, 1, \underline{0}, 0, 0, 0 \rangle \to \langle \underline{0}, 1, 0, 0, 0, 0 \rangle \to \langle 0, \underline{0}, 0, 0, 0, 0 \rangle $$$

В третьем примере каждый элемент уже равен нулю, поэтому никаких операций не требуется.