Madoka and Laziness
Contest: Codeforces Round 777 (Div. 2)
Difficulty rating: 3100
Tags: dp, greedy

Madoka has become too lazy to write a legend, so let's go straight to the formal description of the problem.

An array of integers $$$a_1, a_2, \ldots, a_n$$$ is called a hill if it is not empty and there is an index $$$i$$$ in it, for which the following is true: $$$a_1 < a_2 < \ldots < a_i > a_{i + 1} > a_{i + 2} > \ldots > a_n$$$.

A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deletion of several (possibly, zero or all) elements keeping the order of the other elements. For example, for an array $$$[69, 1000, 228, -7]$$$ the array $$$[1000, -7]$$$ is a subsequence, while $$$[1]$$$ and $$$[-7, 1000]$$$ are not.

Splitting an array into two subsequences is called good if each element belongs to exactly one subsequence, and also each of these subsequences is a hill.

You are given an array of distinct positive integers $$$a_1, a_2, \ldots a_n$$$. It is required to find the number of different pairs of maxima of the first and second subsequences among all good splits. Two pairs that only differ in the order of elements are considered same.

Input format:
The first line of input contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — array size.

The second line of input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array. It is guaranteed that all $$$a_i$$$ are pairwise distinct.

Output format:
In a single line, print exactly one number — the number of different pairs of maxima of the first and second subsequences among all good splits.

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

Note:
In the first test case there are 3 possible pairs: $$$(3, 4)$$$, $$$(2, 4)$$$, $$$(1, 4)$$$. And they are achieved with the following partitions: $$$[1, 2, 3], [4]$$$; $$$[4, 3], [1, 2]$$$; $$$[1], [2, 4, 3]$$$

Example input:
4
1 2 4 3

Example output:
3

Example input:
8
2 12 13 7 14 6 11 8

Example output:
4

Editorial:
The inflection of the subsequence will be called the maximum number in the sequence, and $$$ind$$$ — is the index of the maximum element in the array. Then it is clear that the inflection of one sequence will be the element $$$a_{ind}$$$. Let this be the first sequence and the other be the second.
We will assume that the inflection of the second subsequence is at the position $$$ind2$$$, where $$$ind2 > ind$$$ (since it will be possible to reverse the array and then run the algorithm again).
Then we have $$$3$$$ plots. On the segment $$$(1, ind)$$$ both subsequences increase, on the segment $$$(ind, ind2)$$$ the first subsequence decreases, and the second increases, and on the segment $$$(ind2, n)$$$ both subsequences decrease.
Then let $$$dp1_i$$$ — be the minimum possible maximum element in a subsequence that does not contain $$$i$$$ element. and it's easy to calculate: If $$$dp1_{i - 1} < a_{i}$$$, then $$$dp1_{i} = min(dp1_{i}, a_{i - 1})$$$, since in this case we can add an $$$i$$$ element to a subsequence that does not contain an element of $$$i - 1$$$. Similarly, if $$$a_{i - 1} < a_{i}$$$, then $$$dp1_{i} = min(dp1_{i}, dp1_{i - 1})$$$.
Now let's count the following arrays: $$$dp3_{i, 0}$$$ — the minimum possible last element in the second subsequence if the $$$i$$$ element belongs to the first subsequence. And $$$dp3_{i, 1}$$$ — the maximum possible last element in the first subsequence if the $$$i$$$ element belongs to the second subsequence. There are several options. If $$$i$$$ and $$$i - 1$$$ lie in the same and different subsequences. And we will count for $$$i\leq ind$$$, since both sub-sequences increase up to this section. And then it is not difficult to get the calculate formulas:
• $$$dp3_{ind, 0} = dp1_{ind}$$$, by definition $$$dp3_{ind, 0}$$$
• If $$$a_{i - 1} > a_i$$$, then $$$dp3_{i, 0} = min(dp3_{i, 0}, dp3_{i - 1, 0})$$$.
• If $$$dp3_{i - 1, 1} > a_i$$$, then $$$dp3_{i, 0}= min(dp3_{i, 0}, a_{i - 1})$$$.
• If $$$a_{i - 1} <a_{i}$$$, then $$$dp3_{i, 1}= max(dp3_{i, 1}, dp3_{i - 1, 1})$$$.
• If $$$dp3_{i - 1, 0} < a_i$$$, then $$$dp3_{i, 1}= max(dp3_{i, 1}, a_{i - 1})$$$.
It remains only to calculate $$$dp2_i$$$ — the minimum possible maximum element for a subsequence that does not have an $$$i$$$ element if we took all the elements on the segment $$$(i, n)$$$.
It is considered almost the same way as $$$dp1$$$.
Now it is clear that if $$$i > ind$$$ and $$$dp3_{i, 1}> dp2_{i}$$$, then the element $$$i$$$ can be an inflection for the second subsequence, since we have correctly calculated up to $$$i$$$ of the element, and we can keep with the remaining part, so that both subsequences are slides. So you just need to add $$$1$$$ to the answer.