A11941. Median on Segments (Permutations Edition)

You are given a permutation $p_1, p_2, \dots, p_n$ . A permutation of length $n$ is a sequence such that each integer between $1$ and $n$ occurs exactly once in the sequence.

Find the number of pairs of indices $(l, r)$ ( $1 \le l \le r \le n$ ) such that the value of the median of $p_l, p_{l+1}, \dots, p_r$ is exactly the given number $m$ .

The median of a sequence is the value of the element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is used.

For example, if $a=[4, 2, 7, 5]$ then its median is $4$ since after sorting the sequence, it will look like $[2, 4, 5, 7]$ and the left of two middle elements is equal to $4$ . The median of $[7, 1, 2, 9, 6]$ equals $6$ since after sorting, the value $6$ will be in the middle of the sequence.

Write a program to find the number of pairs of indices $(l, r)$ ( $1 \le l \le r \le n$ ) such that the value of the median of $p_l, p_{l+1}, \dots, p_r$ is exactly the given number $m$ .

The first line contains integers $n$ and $m$ ( $1 \le n \le 2\cdot10^5$ , $1 \le m \le n$ ) — the length of the given sequence and the required value of the median.

The second line contains a permutation $p_1, p_2, \dots, p_n$ ( $1 \le p_i \le n$ ). Each integer between $1$ and $n$ occurs in $p$ exactly once.

Print the required number.

In the first example, the suitable pairs of indices are: $(1, 3)$ , $(2, 2)$ , $(2, 3)$ and $(2, 4)$ .