Description

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

Input

第一行为两个正整数n和b ，第二行为1~n 的排列。

Output

输出一个整数，即中位数为b的连续子序列个数。

Sample Input

7 4

5 7 2 4 3 1 6

Sample Output

4

HINT

第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}

N<=100000

 

一开始是想从中位数往两边扩展

后来证伪了……

我们发现数的贡献只和其与中位数大小有关，和其本身是无关的

我们把小于中位数的值设为-1，大于的设为1

显然若区间[l,r]包含中位数且值和为0，那么就是满足条件的

（为什么能保证是奇数长？因为偶数不可能加出和为0的……）

若要判断[l,r]区间，需要sum[r]-sum[l-1]=0,即sum[r]=sum[l-1]

我们将[0,pos-1]的sum值放到一个桶里，然后枚举右端点统计答案即可。

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include