题目描述

有一个长度为 $n$ 的排列 $a$，初始可以任意染白一个数，然后接下来每一步可以染白最小的一个与已经被染白的数相邻的数，显然 $n$ 步之后所有数都会被染白。

现在我们称满足以下要求的数对 $(i,j)$ 是好的数对：

• $1\leq i\leq j\leq n$。
• 存在一个 $k$，满足若从 $a_i$ 开始染白，$a_j$ 会在第 $k$ 步被染白；若从 $a_j$ 开始染白，$a_i$ 也会在第 $k$ 步被染白。

求好的数对的数量。

输入格式

由于输入数据过大，现给出数据辅助生成器。

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$ 开始，不要忘记规定数组大小。

输出格式

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

5 114514

9

10 113037

23

20 73555

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)$。

数据范围

「本题采用捆绑测试」

对于 $100\%$ 的数据，保证 $1\le n\le 10^7$，$0\leq s\leq 114514$，$a$ 为 $n$ 的排列。

特殊性质 $\text{A}$：$a_i$ 单调递增，此时 $s=0$。