P10371 「LAOI-4」石头

有一个长度为 $n$ 的排列 $a$，初始可以任意染白一个数，然后接下来每一步可以染白最小的一个与已经被染白的数相邻的数，显然 $n$ 步之后所有数都会被染白。 现在我们称满足以下要求的数对 $(i,j)$ 是好的数对： - $1\leq i\leq j\leq n$。 - 存在一个 $k$，满足若从 $a_i$ 开始染白，$a_j$ 会在第 $k$ 步被染白；若从 $a_j$ 开始染白，$a_i$ 也会在第 $k$ 步被染白。 求好的数对的数量。

无

无

### 样例解释 对于样例组 #1，$a=\{4,3,1,5,2\}$，好的数对分别是：$(1,1),(1,3),(1,5),(2,2),(2,3),(2,4),(3,3),(4,4),(5,5)$。 ### 数据范围 **「本题采用捆绑测试」** |子任务编号|$n$|特殊性质|分值| |:-:|:-:|:-:|:-:| |$1$|$\le10^3$|无|$15$| |$2$|$\le10^5$|无|$30$| |$3$|$\le10^7$|$\text{A}$|$5$| |$4$|$\le10^7$|无|$50$| 对于 $100\%$ 的数据，保证 $1\le n\le 10^7$，$0\leq s\leq 114514$，$a$ 为 $n$ 的排列。 特殊性质 $\text{A}$：$a_i$ 单调递增，此时 $s=0$。