Median on Segments (Permutations Edition)

题意翻译

#### 题目翻译 给定1~n的排列$(1<=n<=2*10^5)$，求中位数为m的字段个数（子段长度为偶数时，去其第k/2项，k为子段长度） #### 输入格式 第一行两个整数，n，m 第二行为n的排列 #### 输出格式 输出满足要求的方案数

题目描述

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.

输入输出样例

输入样例 #1

5 4
2 4 5 3 1

输出样例 #1

4

输入样例 #2

5 5
1 2 3 4 5

输出样例 #2

1

输入样例 #3

15 8
1 15 2 14 3 13 4 8 12 5 11 6 10 7 9

输出样例 #3

48

说明

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