P10371 "LAOI-4" Stones

There is a permutation $a$ of length $n$. At the beginning, you may choose any one number to paint white. Then, at each next step, you may paint white the smallest number that is adjacent to any already-white number. Clearly, after $n$ steps, all numbers will be painted white. Now we call a pair $(i,j)$ a good pair if it satisfies the following: - $1\leq i\leq j\leq n$. - There exists a $k$ such that: if you start painting white from $a_i$, then $a_j$ will be painted white at step $k$; and if you start painting white from $a_j$, then $a_i$ will also be painted white at step $k$. Find the number of good pairs.

Because the input is too large, a helper generator is provided. ```cpp int a[/*数组大小*/]; namespace GenHelper { unsigned z1, z2, z3, z4, b; unsigned rand_() { b = ((z1 > 13; z1 = ((z1 & 4294967294U) 27; z2 = ((z2 & 4294967288U) 21; z3 = ((z3 & 4294967280U) 12; z4 = ((z4 & 4294967168U)

Output one positive integer in one line, representing the number of good pairs.

### Sample Explanation For sample group #1, $a=\{4,3,1,5,2\}$. The good pairs are: $(1,1),(1,3),(1,5),(2,2),(2,3),(2,4),(3,3),(4,4),(5,5)$. ### Constraints **"This problem uses bundled tests."** |Subtask ID|$n$|Special property|Score| |:-:|:-:|:-:|:-:| |$1$|$\le10^3$|None|$15$| |$2$|$\le10^5$|None|$30$| |$3$|$\le10^7$|$\text{A}$|$5$| |$4$|$\le10^7$|None|$50$| For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^7$, $0\leq s\leq 114514$, and $a$ is a permutation of $n$. Special property $\text{A}$: $a_i$ is strictly increasing, and in this case $s=0$. Translated by ChatGPT 5