Median of a Contiguous Subsequence

Time limit1sMemory limit128 MB

Summary

Count odd-length contiguous subarrays of a permutation of 1..N whose median equals a given value B.

Level: Medium7 of 10
Topics: Prefix sum, Hash map, Array
Solved: No attempts yet

Problem

You are given a sequence A of length N consisting of the distinct natural numbers from 1 through N. Each number appears exactly once.

A contiguous subsequence of A is a non-empty sequence obtained by removing zero or more elements from the front and zero or more elements from the back.

Count the contiguous subsequences whose length is odd and whose median is B. The median is the middle value after sorting the elements in increasing order. For example, the median of {5, 1, 3} is 3.

Input

The first line contains two integers N and B. (1 <= N <= 100,000, 1 <= B <= N)

The second line contains the N elements of A separated by spaces.

Output

Print the number of odd-length contiguous subsequences whose median is B.

Examples3

Example 1
Input
```
7 4
5 7 2 4 3 1 6
```
Expected output
```
4
```
Example 2
Input
```
6 3
1 2 4 5 6 3
```
Expected output
```
1
```
Example 3
Input
```
5 4
1 2 3 4 5
```
Expected output
```
2
```