## COCI '07 Contest 1 #5 Srednji

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

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

5 4
1 2 3 4 5

#### Sample Output 1

2

#### Sample Input 2

6 3
1 2 4 5 6 3

#### Sample Output 2

1

#### Sample Input 3

7 4
5 7 2 4 3 1 6

#### Sample Output 3

4

#### Explanation for Sample Output 3

In the third example, the four subsequences of with median are , , and .