1871: 中位数

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:13 通过:9

题目描述

农民约翰(Farmer John)把他的 N 头奶牛排成一排,以便测量它们的高度。
每头奶牛的高度是 Hi。
他想要拍摄一张照片,展示连续的一些奶牛来参加一场乡村博览会上的牛类摄影比赛。
比赛有一个奇怪的规定:只有当照片显示出一组奶牛中位数高度至少为 X 时才能参赛。
为了解决这个问题,我们定义数组 A[0...K] 的中位数为经过排序后的 A[ceiling(K/2)]。
其中 ceiling(K/2) 是将 K/2 上取整得到的整数,如果 K/2 本身就是整数,则中位数为 A[K/2]。
例如,{7, 3, 2, 6} 的中位数为 6,{5, 4, 8} 的中位数为 5。
请帮助约翰计算有多少不同的连续子序列的中位数高度至少为 X,以便他可以提交这些奶牛的照片参赛。

输入格式

第一行为正整数 N 和 X 。(1 <= N <= 100,000,1 <= X <= 1,000,000,000
接下来 N 行为 N 头牛的高度 Hi 。(1 <= Hi <= 1,000,000,000)

输出格式

输出一个数字表示答案。

输入样例 复制

4 6
10
5
6
2

输出样例 复制

7

数据范围与提示

来源:USACO 2011.11