## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Decinc Dividing Codeforces Solution | Codeforces Problem Solution 2022

F. Decinc Dividing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's call an array $a$ of $m$ integers ${a}_{1},{a}_{2},\dots ,{a}_{m}$ Decinc if $a$ can be made increasing by removing a decreasing subsequence (possibly empty) from it.

• For example, if $a=\left[3,2,4,1,5\right]$, we can remove the decreasing subsequence $\left[{a}_{1},{a}_{4}\right]$ from $a$ and obtain $a=\left[2,4,5\right]$, which is increasing.

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

Input

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},\dots ,{p}_{n}$ ($1\le {p}_{i}\le n$, all ${p}_{i}$ are distinct)  — elements of the permutation.
Output the number of pairs of integers $\left(l,r\right)$ such that $p\left[l\dots r\right]$ (the subarray of $p$ from $l$ to $r$) is a Decinc array.