Consider a sequence
of integers, containing
integers between
and
. Each integer appears exactly once in the sequence.
A subsequence of
is a sequence obtained by removing some (possibly none) numbers from the beginning of
, and then from the end of
. Calculate how many different subsequences of
of odd length have their median equal to
. 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
is
.
Input Specification
The first line contains two integers,
and
.
The second line contains
integers separated by spaces, the elements of sequence
.
Output Specification
Output the number of subsequences of
whose median is
.
Sample Input 1
Copy
5 4
1 2 3 4 5
Sample Output 1
Copy
2
Sample Input 2
Copy
6 3
1 2 4 5 6 3
Sample Output 2
Copy
1
Sample Input 3
Copy
7 4
5 7 2 4 3 1 6
Sample Output 3
Copy
4
Explanation for Sample Output 3
In the third example, the four subsequences of
with median
are
,
,
and
.
Comments
I currently have an
algorithm in Python. Is there a better time complexity in which I can solve it? or is Python just too slow for this problem?
Since
, 
can be 
in a worst case, which is too slow.