#USACOC1111A. Above the Median

Above the Median

Farmer John 将他的 NN 头奶牛排成了一排,以测量它们的身高;第 ii 头奶牛的身高为 HiH_i 纳米——FJ 相信测量是精确的。他想对其中连续的几段奶牛拍照片,并使用这些照片参加县集会上的奶牛摄影比赛。

对于所有提交的照片,集会都有一个奇怪的规定:一张照片有效,当且仅当照片中的这些奶牛身高的中间值至少为 XX

为简化题意,我们定义一个序列 A0KA_{0\ldots K} 的中间值为将序列 AA 排序后的 AK2A_{\left\lceil \frac{K}{2}\right\rceil},其中 K2\left\lceil \frac{K}{2}\right\rceil 表示 K2\frac{K}{2} 向上取整。例如,序列 {7,3,2,6}\{7, 3, 2, 6\} 的中间值为 66,序列 {5,4,8}\{5, 4, 8\} 的中间值为 55

请帮助 FJ 算出他可以在他的这排奶牛拍出多少张不同的照片用于参加奶牛摄影比赛。

  • 1N100,0001 \leqslant N \leqslant 100,000
  • 1Hi1,000,000,0001 \leqslant H_i \leqslant 1,000,000,000
  • 1X1,000,000,0001 \leqslant X \leqslant 1,000,000,000

输入格式

  • 11 行:两个用空格隔开的整数:NNXX
  • 2..N+12..N+1 行:第 i+1i+1 行包含一个单独的整数 HiH_i

输出格式

  • 11 行:在 FJ 的这排奶牛中符合身高中间值不小于 XX 的子段数量。注意答案可能超过 32 位整数的表示范围。
4 6
10
5
6
2
7

输入细节

FJ 的四头牛身高分别为 1010556622。我们希望知道有多少连续的奶牛子段满足其身高的中间值至少为 66.

输出细节

一共有 1010 个子段,其中有 77 个子段的中间值至少为 66。它们分别是 {10}\{10\}{6}\{6\}{10,5}\{10, 5\}{5,6}\{5, 6\}{6,2}\{6, 2\}{10,5,6}\{10, 5, 6\}{10,5,6,2}\{10, 5, 6, 2\}