有一个长度为 $n$ 的排列 $a$，初始可以任意染白一个数，然后接下来每一步可以染白最小的一个与已经被染白的数相邻的数，显然 $n$ 步之后所有数都会被染白。
现在我们称满足以下要求的数对 $(i,j)$ 是好的数对：
- $1\leq i\leq j\leq n$。
- 存在一个 $k$，满足若从 $a_i$ 开始染白，$a_j$ 会在第 $k$ 步被染白；若从 $a_j$ 开始染白，$a_i$ 也会在第 $k$ 步被染白。
求好的数对的数量。
## Input
由于输入数据过大，现给出数据辅助生成器。
```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$ 开始，不要忘记规定数组大小。
## Output
共一行一个正整数，表示好的数对的数量。
[samples]
## Note
### 样例解释
对于样例组 #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$。