Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

KMEDIAN - Above the Median

no tags 

Farmer John has lined up his N (1 ≤ N ≤ 100,000) cows in a row to measure their heights; cow i has height H_i (1 ≤ H_i ≤ 1,000,000,000) nanometers--FJ believes in precise measurements! He wants to take a picture of some contiguous subsequence of the cows to submit to a bovine photography contest at the county fair.

The fair has a very strange rule about all submitted photos: a photograph is only valid to submit if it depicts a group of cows whose median height is at least a certain threshold X (1 ≤ X ≤ 1,000,000,000).

For purposes of this problem, we define the median of an array A[0...K] to be A[ceiling(K/2)] after A is sorted, where ceiling(K/2) gives K/2 rounded up to the nearest integer (or K/2 itself, it K/2 is an integer to begin with). For example the median of {7, 3, 2, 6} is 6, and the median of {5, 4, 8} is 5.

Please help FJ count the number of different contiguous subsequences of his cows that he could potentially submit to the photography contest.

Input

  • Line 1: Two space-separated integers: N and X.
  • Lines 2..N+1: Line i+1 contains the single integer H_i.

Output

  • Line 1: The number of subsequences of FJ's cows that have median at least X. Note this may not fit into a 32-bit integer.

Example

Input:
4 6
10
5
6
2


Output:
7

Explain: There are 10 possible contiguous subsequences to consider. Of these, only 7 have median at least 6. They are {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.


Added by:khanhptnk
Date:2011-11-19
Time limit:0.302s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:USACO November 2011