Problem Description

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.

Input Format

Because the input is too large, a helper generator is provided.

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;
    }
}

The input contains two integers $n$ and $s$, representing the permutation length and the random seed, respectively.

You must call srand_(s,n) exactly once. After that, $a_i$ is already stored in a[i]. Note that the index starts from $1$. Do not forget to set the array size.

Output Format

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

5 114514

9

10 113037

23

20 73555

49

Hint

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."

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