У Yeri есть массив из \(n + 2\) неотрицательных целых чисел: \(a_0, a_1, ..., a_n, a_{n + 1}\).
Мы знаем, что \(a_0 = a_{n + 1} = 0\).
Она хочет сделать все элементы \(a\) равными нулю за минимальное количество операций.
За одну операцию она может сделать одно из следующих действий:
- Выбрать самый левый максимальный элемент и изменить его на максимальный из элементов слева от него.
- Выбрать самый правый максимальный элемент и изменить его на максимальный из элементов справа от него.
Помогите ей найти минимальное количество операций, необходимых для того, чтобы все элементы \(a\) стали равны нулю.
Примечание
В первом примере вы получите \(\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 \)
В третьем примере каждый элемент уже равен нулю, поэтому никаких операций не требуется.