CF1005E1.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$.

给你一个排列 $p_1, p_2, \dots, p_n$。长度为 $n$ 的排列是指由 $1$ 到 $n$ 之间的每个整数恰好出现一次所构成的序列。

请找出满足如下条件的下标对 $(l, r)$（其中 $1 \le l \le r \le n$）的个数：子序列 $p_l, p_{l+1}, \dots, p_r$ 的中位数恰好等于给定的数 $m$。

一个序列的中位数定义为：将该序列按非递减顺序排序后，位于中间位置的元素的值。若序列长度为偶数，则取中间两个元素中靠左的那个。

例如，若 $a=[4, 2, 7, 5]$，则其排序后为 $[2, 4, 5, 7]$，中间两个元素为 $4$ 和 $5$，取左侧的 $4$，因此中位数为 $4$；又如 $[7, 1, 2, 9, 6]$ 排序后为 $[1, 2, 6, 7, 9]$，中间元素为 $6$，故中位数为 $6$。

请编写程序，计算满足条件的下标对 $(l, r)$（其中 $1 \le l \le r \le n$）的个数，使得子序列 $p_l, p_{l+1}, \dots, p_r$ 的中位数恰好等于给定的数 $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.

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2\cdot10^5$，$1 \le m \le n$）—— 分别表示给定序列的长度以及所要求的中位数值。

第二行包含一个排列 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）。$1$ 到 $n$ 之间的每个整数在 $p$ 中恰好出现一次。

Print the required number.

输出所需的数字。

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

在第一个例子中，合适的索引对为：$(1, 3)$、$(2, 2)$、$(2, 3)$ 和 $(2, 4)$。