[ABC107D] Median of Medians
题意翻译
## 题目描述
定义一个长度为 $M$ 的序列的中位数为这个序列中第 $\lfloor\frac M 2\rfloor + 1$ 小的数。
现在有一个长度为 $N$ 的序列 $A$,将 $A$ 的所有子段的中位数取出来作为一个序列 $S$,问序列 $S$ 的中位数是多少。
## 说明/限制
$\begin{array}{l}1\le N\le 10^5\\1\le A_i\le 10^9\end{array}$
**样例1解释**
所有可能的子段为 $[10],[30],[20],[10,30],[30,20],[10,30,20]$,它们的中位数分别为 $10,30,20,30,30,20$,而 $[10,30,20,30,30,20]$ 的中位数为 $30$,因此答案为 $30$。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc107/tasks/arc101_b
長さ $ M $ の数列 $ b $ の **中央値** を次のように定義します。
- $ b $ を昇順にソートして得られる数列を $ b' $ とする。 このとき、$ b' $ の $ M\ /\ 2\ +\ 1 $ 番目の要素の値を、$ b $ の中央値とする。 ここで、$ / $ は小数点以下を切り捨てる除算である。
例えば、$ (10,\ 30,\ 20) $ の中央値は $ 20 $ であり、$ (10,\ 30,\ 20,\ 40) $ の中央値は $ 30 $ であり、$ (10,\ 10,\ 10,\ 20,\ 30) $ の中央値は $ 10 $ です。
すぬけ君は次のような問題を思いつきました。
長さ $ N $ の数列 $ a $ があります。 各 $ (l,\ r) $ ($ 1\ \leq\ l\ \leq\ r\ \leq\ N $) について、$ a $ の連続部分列 $ (a_l,\ a_{l\ +\ 1},\ ...,\ a_r) $ の中央値を $ m_{l,\ r} $ とします。 すべての $ (l,\ r) $ に対する $ m_{l,\ r} $ を並べ、新たに数列 $ m $ を作ります。 $ m $ の中央値を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $
输出格式
$ m $ の中央値を出力せよ。
输入输出样例
输入样例 #1
3
10 30 20
输出样例 #1
30
输入样例 #2
1
10
输出样例 #2
10
输入样例 #3
10
5 9 5 9 8 9 3 5 4 3
输出样例 #3
8
说明
### 制約
- $ 1\ \leq\ N\ \leq\ 10^5 $
- $ a_i $ は整数である。
- $ 1\ \leq\ a_i\ \leq\ 10^9 $
### Sample Explanation 1
$ a $ のそれぞれの連続部分列の中央値は次のようになります。 - $ (10) $ の中央値は $ 10 $ - $ (30) $ の中央値は $ 30 $ - $ (20) $ の中央値は $ 20 $ - $ (10,\ 30) $ の中央値は $ 30 $ - $ (30,\ 20) $ の中央値は $ 30 $ - $ (10,\ 30,\ 20) $ の中央値は $ 20 $ よって、$ m\ =\ (10,\ 30,\ 20,\ 30,\ 30,\ 20) $ となり、$ m $ の中央値は $ 30 $ です。