Outermost Maximums
Contest: Codeforces Round 800 (Div. 1)
Difficulty rating: 3400
Tags: data structures, greedy

Yeri has an array of $$$n + 2$$$ non-negative integers : $$$a_0, a_1, ..., a_n, a_{n + 1}$$$.

We know that $$$a_0 = a_{n + 1} = 0$$$.

She wants to make all the elements of $$$a$$$ equal to zero in the minimum number of operations.

In one operation she can do one of the following:

- Choose the leftmost maximum element and change it to the maximum of the elements on its left.
- Choose the rightmost maximum element and change it to the maximum of the elements on its right.

Help her find the minimum number of operations needed to make all elements of $$$a$$$ equal to zero.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).

Output format:
Print a single integer  — the minimum number of operations needed to make all elements of $$$a$$$ equal to zero.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, you get $$$\langle 1, \underline{1}, 2, 4, 0, 2 \rangle$$$ by performing the first operation and $$$\langle 1, 4, 2, \underline{2}, 0, 2 \rangle$$$ by performing the second operation.

One way to achieve our goal is shown below. (The underlines show the last change.) $$$\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 $$$

In the third sample each element is already equal to zero so no operations are needed.

Example input:
6
1 4 2 4 0 2

Example output:
7

Example input:
5
1 3 5 4 2

Example output:
9

Editorial:
Let's calculate for each element of the array, the minimum number of times it needs to change throughout the process.
Let's take a look at the first time the $$$i$$$-th element is changing. We know that $$$a_i$$$ is the maximum number and the elements smaller than $$$a_i$$$ haven't changed yet.
Denote the maximum element on its left as $$$l$$$ and the maximum element on its right as $$$r$$$.
So $$$l$$$ is equal to the largest number among $$$a_1, a_2, \ldots, a_{i - 1}$$$ that is smaller than $$$a_i$$$. Likewise for $$$r$$$.
We can change $$$a_i$$$ to either $$$l$$$ or $$$r$$$. It's better to change it to the smaller one. (We'll get into the details of why this is correct later.)
Let $$$c_i$$$ be the minimum number of times the $$$i$$$-th element needs to change. The following greedy algorithm works in $$$\sum c_i$$$ operations.
Let $$$x$$$ be the number the leftmost maximum becomes if we do the first operation and $$$y$$$ be the number the rightmost maximum becomes if we do the second operation.
Do the first operation if $$$x \leq y$$$ and do the second operation otherwise. If $$$x \leq y$$$ then for the leftmost maximum, the maximum element on its left is smaller than the maximum element on its right. That means we are making the right choice for this element.
Let's assume the array is a permutation of numbers from $$$1$$$ through $$$n$$$ for simplicity.
For some element $$$a_i$$$ make string $$$S$$$ of length $$$n$$$ such that
• $$$S_{a_i}$$$ = "O".
• for any $$$j < i$$$, $$$S_{a_j}$$$ = "L".
• for any $$$j > i$$$, $$$S_{a_j}$$$ = "R".
Imagine Yeri is initially standing on the $$$a_i$$$-th character of S (which is "O") and she is facing the beginning of the string.
In each step she either jumps to the nearest "L" or jumps to the nearest "R". And her goal is to jump out of the string in minimum number of jumps. We know it's always better to jump to the further one, but we won't need this fact.
We will use a segment tree. For each node maintain 4 values. What is the minimum possible number of jumps made in this interval in case
• we enter it looking for an "L" and leave it looking for an "L"
• we enter it looking for an "L" and leave it looking for an "R"
• we enter it looking for an "R" and leave it looking for an "L"
• we enter it looking for an "R" and leave it looking for an "R"
It's easy to update this. Just fix which character you are looking for when moving from the node's one child to the other. And you can find these values for intervals of length $$$1$$$.
Now if you iterate over $$$i$$$ from $$$1$$$ to $$$n$$$. At each step at most 2 characters of the string are changing, hence you can keep your segment tree updated.
But there are still some details we need to sort out. The array is not necessarily a permutation. To fix this, first get rid of the "O". Then for each number see if it appears on the left side and see if it appears on the right side. Now there are 4 different states for each number but the same segment tree can handle this too. We just need to find the 4 values for each of the 4 states of a single number.
Time complexity: $$$\mathcal{O}(n\log n)$$$