Max to the Right of Min
Contest: Educational Codeforces Round 152 (Rated for Div. 2)
Difficulty rating: 2300
Tags: binary search, data structures, divide and conquer, dp, dsu, two pointers

You are given a permutation $$$p$$$ of length $$$n$$$ — an array, consisting of integers from $$$1$$$ to $$$n$$$, all distinct.

Let $$$p_{l,r}$$$ denote a subarray — an array formed by writing down elements from index $$$l$$$ to index $$$r$$$, inclusive.

Let $$$\mathit{maxpos}_{l,r}$$$ denote the index of the maximum element on $$$p_{l,r}$$$. Similarly, let $$$\mathit{minpos}_{l,r}$$$ denote the index of the minimum element on it.

Calculate the number of subarrays $$$p_{l,r}$$$ such that $$$\mathit{maxpos}_{l,r} > \mathit{minpos}_{l,r}$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of elements in the permutation.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$). All $$$p_i$$$ are distinct.

Output format:
Print a single integer — the number of subarrays $$$p_{l,r}$$$ such that $$$\mathit{maxpos}_{l,r} > \mathit{minpos}_{l,r}$$$.

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

Example input:
3
1 2 3

Example output:
3

Example input:
6
5 3 6 1 4 2

Example output:
4

Editorial:
The problem was originally prepared as part of the lecture on a monotonic stack. Thus, I will omit its explanation.
First, recall a common technique of counting all segments satisfying some property. You can count the segments that have the same right border at the same time.
Consider all segments $$$[l, r]$$$ with a fixed $$$r$$$. How do the minimums and the maximums on them change from each other? If you look at the segments in the order of decreasing $$$l$$$, we can write down the sequence of the following events: the minimum becomes smaller or the maximum becomes larger. In fact, we can maintain both of these types with two monotonic stacks.
Now, which $$$l$$$ correspond to good segments with regard to the events? Consider two adjacent events $$$(i_1, t_1)$$$ and $$$(i_2, t_2)$$$, where $$$i_j$$$ is the index of the event and $$$t_j$$$ is the type ($$$0$$$ for min, $$$1$$$ for max). It's easy to see that if $$$t_2 = 0$$$, then all segments that have $$$l$$$ from $$$i_1 + 1$$$ to $$$i_2$$$ are good. It means that, while going from right to left, the last event we encountered was the minimum getting smaller. Thus, the index of the minimum becomes to the left from the index of the maximum.
As for the implementation, we will maintain these events in a set of pairs: (index of the event, type of the event). This way, it's not that hard to maintain the sum of distances from each event of type $$$0$$$ to the left to the previous event.
When you erase an event, only a few distances can be affected: the distance from the next one to the current one, from the current one to the previous one and the newly created distance from the next one to the previous one. Just check for the types. When you add an event, you only add it to the very end of the set, so it's trivial to recalculate.
That will be $$$O(n \log n)$$$ just from the set, the monotonic stacks by themselves are linear.
You can optimize this solution to $$$O(n)$$$ by using a doubly-linked list, but it really was not necessary for the problem.
There's also a different solution for which you can maintain the intervals of good values $$$l$$$ explicitly. First, compress them in such a way that the segments don't touch at borders. Now, you can notice that by going from $$$r$$$ to $$$r+1$$$ we can only affect the rightmost ones of them: possibly remove some, then change the last one and add a new one. So we can actually simulate this behavior with another stack. The details are left as an exercise to a reader. With the correct implementation, this solution will be $$$O(n)$$$.