CR08C1P5 - SREDNJI
Consider a sequence A of integers, containing N integers between 1 and N. Each integer appears exactly once in the sequence.
A subsequence of A is a sequence obtained by removing some (possibly none) numbers from the beginning of A, and then from the end of A.
Calculate how many different subsequences of A of odd length have their median equal to B. The median of a sequence is the element in the middle of the sequence after it is sorted. For example, the median of the sequence {5, 1, 3} is 3.
Input
The first line contains two integers, N (1 ≤ N ≤ 100000) and B (1 ≤ B ≤ N).
The second line contains N integers separated by spaces, the elements of sequence A.
Output
Output the number of subsequences of A whose median is B.
Example
Input: 5 4 1 2 3 4 5 Output: 2
Input: 6 3 1 2 4 5 6 3 Output: 1
Input: 7 4 5 7 2 4 3 1 6 Output: 4
In the third example, the four subsequences of A with median 4 are {4}, {7, 2, 4}, {5, 7, 2, 4, 3} and {5, 7, 2, 4, 3, 1, 6}.
Added by: | Ahmed Salem [mrtempo] |
Date: | 2015-01-23 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 JS-MONKEY |
Resource: | COCI 2007/2008 #1 (http://hsin.hr/coci/archive/2007_2008/contest1_tasks.pdf) |