← 返回题目列表

AtCoder · arc101_b

D. 中位数的中位数

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

我们将定义 序列的 中位数 长度为 $$$n$$$ 的数组 $$$a$$$ 的 一个序列的 b 长度 M,如下:

  • 让 b' 为排序得到的序列 b 按非降序排列。那么,的值 (M / 2 + 1)- 第一个元素 b' 是中位数 b。在这里, / 是整数除法,向下舍入。

例如,中位数 (10, 30, 20) is 20;的中位数 (10, 30, 20, 40) is 30;的中位数 (10, 10, 10, 20, 30) is 10.

Snuke 出现以下问题。

给你一个序列 a 长度 N。 对于每对 (l, r) (1 \leq l \leq r \leq N),让 m_{l, r} 是连续子序列的中位数 (a_l, a_{l + 1}, ..., a_r) of a。 我们将列出 m_{l, r} 对于所有对 (l, r) 创建一个新序列 m。 找出中位数 m.

约束

  • 1 \leq N \leq 10^5
  • a_i 是一个整数。
  • 1 \leq a_i \leq 10^9

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 ... a_N

输出

打印中位数 m.


示例输入 1

3
10 30 20

示例输出 1

30

每个连续子序列的中位数 a 如下:

  • 的中位数 (10) is 10.
  • 的中位数 (30) is 30.
  • 的中位数 (20) is 20.
  • 的中位数 (10, 30) is 30.
  • 的中位数 (30, 20) is 30.
  • 的中位数 (10, 30, 20) is 20.

因此, m = (10, 30, 20, 30, 30, 20) 和中位数 m is 30.


示例输入 2

1
10

示例输出 2

10

示例输入 3

10
5 9 5 9 8 9 3 5 4 3

示例输出 3

8