#P1005E2. Median on Segments (General Case Edition)
Median on Segments (General Case Edition)
Description
You are given an integer sequence $a_1, a_2, \dots, a_n$.
Find the number of pairs of indices $(l, r)$ ($1 \le l \le r \le n$) such that the value of median of $a_l, a_{l+1}, \dots, a_r$ is exactly the given number $m$.
The median of a sequence is the value of an 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 median of $a_l, a_{l+1}, \dots, a_r$ is exactly the given number $m$.
The first line contains integers $n$ and $m$ ($1 \le n,m \le 2\cdot10^5$) — the length of the given sequence and the required value of the median.
The second line contains an integer sequence $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2\cdot10^5$).
Print the required number.
Input
The first line contains integers $n$ and $m$ ($1 \le n,m \le 2\cdot10^5$) — the length of the given sequence and the required value of the median.
The second line contains an integer sequence $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2\cdot10^5$).
Output
Print the required number.
Samples
5 4
1 4 5 60 4
8
3 1
1 1 1
6
15 2
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
97
Note
In the first example, the suitable pairs of indices are: $(1, 3)$, $(1, 4)$, $(1, 5)$, $(2, 2)$, $(2, 3)$, $(2, 5)$, $(4, 5)$ and $(5, 5)$.