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

[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$a$ of m$m$ integers a1,a2,…,am$a_1,a_2,\dots ,a_m$ Decinc if a$a$ can be made increasing by removing a decreasing subsequence (possibly empty) from it.

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

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

Input

The first line contains a single integer n$n$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$)  — the size of p$p$.

Solution Click Below:-  CLICK HERE

The second line contains n$n$ integers p1,p2,…,pn$p_1,p_2,\dots ,p_n$ (1≤pi≤n$1\le p_i\le n$, all pi$p_i$ are distinct)  — elements of the permutation.

Creep Codeforces Solution

Paranoid String Codeforces Solution

Directional Increase Codeforces Solution

Fake Plastic Trees Codeforces Solution

Keshi in Search of AmShZ Codeforces Solution

Decinc Dividing Codeforces Solution

Output

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