递增递减划分

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

若一个整数序列能够在删除其中一个单调递减子序列（可以为空）后变为单调递增序列，则称该序列是好的。两个子序列均保持原序列中的相对顺序。

给定一个 $1\sim n$ 的排列 $p$，求 $p$ 有多少个子数组是好的。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示一个 $1\sim n$ 的排列。

输出格式

输出一个整数，表示好的子数组数量。

样例输入 1

3
2 3 1

样例输出 1

6

样例输入 2

6
4 5 2 6 1 3

样例输出 2

19

样例输入 3

10
7 10 1 8 3 9 2 4 6 5

样例输出 3

39

样例解释

样例一中所有子数组都是好的。

样例二中，除 $p[1\ldots 6]$ 和 $p[2\ldots 6]$ 外的所有子数组都是好的。

数据范围

对于所有数据，$1\le n\le 2\times 10^5$，$1\le p_i\le n$，且 $p_i$ 两两不同。