TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5607
  • 問題
  • P5607中位数们的中位数
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 1s,256m
    問題説明

     中位数的定义:对于一个长度为n的数列a,将a由小到大排序后,第n/2+1的一项就是a的中位数("/"表示整除)。
     例如:数列(15,33,20)的中位数是20;数列(10,30,20,40)的中位数为30;数列(10,20,10,30,15)的中位数是15;

    何老板想让你帮忙解决下面问题:
      给你一个长度为n的整数数列$A$,对于任意一对整数$[l,r]$ \((1≤l≤r≤n)\),设$M_{l,r}$表示A的子序列$A_l,A_{l+1},...,A_r$的中位数。
      对于$A$所有的子序列$A[l...r]$,我们都找出它的中位数$M_{l,r}$,那么我们将得到一个中位数构成的序列$B$,求出$B$的中位数。

    入力形式

    第一行,一个整数n
    第二行,n个空格间隔的整数$A_1,A_2,...,A_n$

    出力形式

    一个整数,表示所求的中位数

    サンプル入力 1

    3
    10 30 20

    サンプル出力 1

    30

    样例解释:
    子序列(10)的中位数是10
    子序列(30)的中位数是30
    子序列(20)的中位数是20
    子序列(10,30)的中位数是30
    子序列(30,20)的中位数是30
    子序列(10,30,20)的中位数是20  
    得到的中位数序列B=(10,30,20,30,30,20),中位数为30

    サンプル入力 2

    10
    5 9 5 9 8 9 3 5 4 3

    サンプル出力 2

    8

    ヒント

    $1≤n≤105$
    $1≤A_i≤10
    9$


    ソース  arc101b Median of Medians