Problem Description

There is a permutation \( a \) of length \( n \). Initially, any number can be painted white, and then in each subsequent step, the smallest number adjacent to a number that has already been painted white can be painted white. Obviously, after \( n \) steps, all numbers will be painted white.

Now, we define a pair of numbers \( (i, j) \) as a good pair if the following conditions are met:

• \( 1 \leq i \leq j \leq n \).
• There exists a \( k \) such that if \( a_i \) is the starting point for painting white, \( a_j \) will be painted white in the \( k \)-th step; and if \( a_j \) is the starting point for painting white, \( a_i \) will also be painted white in the \( k \)-th step.

Determine the number of good pairs.

Input Format

Due to the large size of the input data, a data auxiliary generator is provided.

int a[/*array size*/];
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;
    }
}

Input consists of two integers \( n \) and \( s \), representing the length of the permutation and the random seed, respectively.

You need to call srand_(s, n) exactly once. After this, \( a_i \) will be stored in a[i], with indices starting from 1. Do not forget to specify the array size.

Output Format

Output a single positive integer, representing the number of good pairs.

Sample Input and Output

Sample Input #1

5 114514

Sample Output #1

9

Sample Input #2

10 113037

Sample Output #2

23

Sample Input #3

20 73555

Sample Output #3

49

Notes

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) \).

Data Range

This problem uses batched testing.

For 100% of the data, it is guaranteed that \( 1 \le n \le 10^7 \), \( 0 \le s \le 114514 \), and \( a \) is a permutation of \( n \).

Special Condition \( \text{A} \): \( a_i \) is monotonically increasing, in which case \( s = 0 \).

见题面 Input 部分

见题面 Output 部分