Decinc Dividing
Contest: Codeforces Round 800 (Div. 1)
Difficulty rating: 2800
Tags: brute force, data structures, divide and conquer, dp, greedy

Let's call an array $$$a$$$ of $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$ Decinc if $$$a$$$ can be made increasing by removing a decreasing subsequence (possibly empty) from it.

- For example, if $$$a = [3, 2, 4, 1, 5]$$$, we can remove the decreasing subsequence $$$[a_1, a_4]$$$ from $$$a$$$ and obtain $$$a = [2, 4, 5]$$$, which is increasing.

You are given a permutation $$$p$$$ of numbers from $$$1$$$ to $$$n$$$. Find the number of pairs of integers $$$(l, r)$$$ with $$$1 \le l \le r \le n$$$ such that $$$p[l \ldots r]$$$ (the subarray of $$$p$$$ from $$$l$$$ to $$$r$$$) is a Decinc array.

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

The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct)  — elements of the permutation.

Output format:
Output the number of pairs of integers $$$(l, r)$$$ such that $$$p[l \ldots r]$$$ (the subarray of $$$p$$$ from $$$l$$$ to $$$r$$$) is a Decinc array. $$$(1 \le l \le r \le n)$$$

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

Note:
In the first sample, all subarrays are Decinc.

In the second sample, all subarrays except $$$p[1 \ldots 6]$$$ and $$$p[2 \ldots 6]$$$ are Decinc.

Example input:
3
2 3 1

Example output:
6

Example input:
6
4 5 2 6 1 3

Example output:
19

Editorial:
Let's solve the problem for a single subarray.
Assume the $$$i$$$-th element belongs to the increasing subsequence. Define $$$dp_{l, i}$$$ for the interval $$$[l, i]$$$ as the maximum value the last element of the decreasing subsequence can have. It's $$$+\infty$$$ in case the decreasing subsequence is empty. It's $$$-\infty$$$ if the array is not possible.
Assume the $$$i$$$-th element belongs to the decreasing subsequence. Define $$$pd_{l, i}$$$ for the interval $$$[l, i]$$$ as the minimum value the last element of the increasing subsequence can have. It's $$$-\infty$$$ in case the increasing subsequence is empty. It's $$$+\infty$$$ if the array is not possible.
The interval $$$[l, r]$$$ is not Decinc if and only if $$$dp_{l, r} = -\infty$$$ and $$$pd_{l, r} = +\infty$$$.
Iterate over $$$l$$$ from $$$n$$$ to $$$1$$$ and keep the $$$dp$$$ and $$$pd$$$ values updated (shown in the implementation).
We claim that each $$$dp$$$ or $$$pd$$$ value will change at most three times throughout the algorithm.
For some index $$$i$$$ assume $$$j$$$ is the largest index smaller than $$$i$$$ such that $$$a_j > a_{j + 1}$$$.
$$$dp_i$$$ can only be one of these four values: $$$-\infty, +\infty, a_j, a_{j + 1}$$$.
Because the last element of the decreasing subsequence can't be before the $$$j$$$-th element. And if it's some $$$k$$$ that lies on the interval $$$[j + 2, i - 1]$$$ you can simply move it to the increasing subsequence since both ($$$k - 1$$$)-th and ($$$k + 1$$$)-th elements belong to the increasing subsequence.
The same applies for $$$pd_i$$$.
So the $$$upd$$$ function is called $$$\mathcal{O}(n)$$$ times in total.
Time complexity: $$$\mathcal{O}(n)$$$