「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$ 步被染白。 求好的数对的数量。

输入输出格式

输入格式


由于输入数据过大,现给出数据辅助生成器。 ```cpp int a[/*数组大小*/]; namespace GenHelper { unsigned z1, z2, z3, z4, b; unsigned rand_() { b = ((z1 << 6) ^ z1) >> 13; z1 = ((z1 & 4294967294U) << 18) ^ b; b = ((z2 << 2) ^ z2) >> 27; z2 = ((z2 & 4294967288U) << 2) ^ b; b = ((z3 << 13) ^ z3) >> 21; z3 = ((z3 & 4294967280U) << 7) ^ b; b = ((z4 << 3) ^ z4) >> 12; z4 = ((z4 & 4294967168U) << 13) ^ b; return (z1 ^ z2 ^ z3 ^ z4); } } void srand_(unsigned x, int n) { using namespace GenHelper; z1 = x; z2 = (~x) ^ 0x233333333U; z3 = x ^ 0x1234598766U; z4 = (~x) + 51; for (int i = 1; i <= n; ++i) a[i] = i; if (!x) return; for (int i = 1; i <= n; ++i) { int j = rand_() % i + 1, k; k = a[i], a[i] = a[j], a[j] = k; } } ``` 输入两个整数 $n$ 和 $s$,分别表示排列长度和随机数种子。 你需要恰好调用一次 `srand_(s,n)`,在此之后 $a_i$ 已经储存在 `a[i]` 中,注意下标从 $1$ 开始,不要忘记规定数组大小。

输出格式


共一行一个正整数,表示好的数对的数量。

输入输出样例

输入样例 #1

5 114514

输出样例 #1

9

输入样例 #2

10 113037

输出样例 #2

23

输入样例 #3

20 73555

输出样例 #3

49

说明

### 样例解释 对于样例组 #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$。