/*
                                                            .sIj25dZMDdI1vi            .7sXdBJ          DZP          MQ7
                                                          .LUXSKIJr:.                      :7IE57ivbdgqPgQ: :rr..:.  Lgg
                                                       :IMBgPji.                    .7KPEbbX52ZBBQPPQBBMggDPQQMRBBBBQIQRQ...
                                                     vZBMSr.                   :i:rgBBQBBREZdZDMbPqUvZQDZZZQREISIqdBR17gZb...rr:.
                                                  .UBQIi                    .ir::2BQqjLPPrrrrrJPDdZdZQBgQDZZbIXXPPKuSKLuSMdji  :vvr
                                                .PBZr                    ..ri..vEbY7r77sisdMDEIujPgQZPuYjMMggRgRPLrrr7v7Sq51dd7  .isv.
                                              .XBS.                    .rr:. :X5L77vL77LqZDIYrrsdZKYvr7rrLgPqMgDgDgPurvr1XSrLYjXs   :vY.
                                             UQ5.                    .:r:.  iSJvvvvvrLPRPurrrIZBq7r77LvL77sg7JdRgQgSZdv7vq5vLj:.YK:   .Lr
                                           iBK.                     :i:. ..iIYLvLvL7sdEJLr72QQQMQXYYjssvIZdMqi7UKjPL72g175X7LvUr .Ji.   :7:
                                          PM.                      ::. ....5uvvLvv7JEKvY7YgBP1UMbPXSU1YsJu7sPv7JZ77YYv7PSX5v7YL2v  :.:    i7
                                        :MY                      ::. .:.. rIL7vvL7YESvsvuPS77rvv77vvLLsLYvYv1YvvBSvLjsLrIEUrvvYYKu.  .i.   .7.
                                       vg.                     .r:  ::  ..u17LYL7vPS7sYJ1Y7vvYvLvYYsLsYJYsLYvsvvMMjYsjsvrXZv7LY7.Lur.  ir.   r.
                                      KP                      .r. .:ri.. .ILjuvvv5XvYY1YLvLvsYJLYLsLsLsLJLsLsLLrZZbLssJvYXPRvrLs. .rJi  :Yi   r.
                                     qs                      .:. .ir2PIv:21uu. r1KvsL5JvLYLsLsLsYsLsLJLsLJLsYJYrqZXKvsYsXu UQvrur   i2r  .uv.  r.
                                    Ki                      ..  ivvIIjUJ21us.  .DLjsIUvvsLYLJLsYJLsLsYsYsYJLsYj:PDUbUvJsd:  ZB77j:  .jIJ. .UI:  r.
                                   2i                      ..  JUYI1JJsuJuJ:  .E2J:LqY7YLYLsvJssLJLJYsYJYJLsLJs:QR1qqvL52   .BbrvUs. s12I: .SXr  1.
                                  r7                      .. .DKYU1sususjjLvr.RELs7uuvYLYLYvsuJYsYsYsYJsJLsYssJ.QM1jRJYS2i.  sBur7jj77JsU5i :SSv  Q
                                 .L                      :  7BPL12uusjJusjLsvXQsvJqIYLLYYYvYqU7vJJYssJLJLsYjsJv.5BJvZQsus2Yu:iZBvr7YYjLsY1Ir vU5v :M
                                 v                      : .5Bd7u52XJuJjJjsYvvDP7sIIYJvsvYv7E1::vIsuJUuJYjLs77YrirDu7SBbvuJuYJrUQgr77LLsYJsU17 IYPi Ss
                                :i                     . rgBg7jS2KUssuJuJJY75Q2v1KsuLLLYL7UB7r::71sJri:51rr7rLrd.PJL5vP5Ljjs777gEPrvvJLsLsYu1::qud. M
                                i                     ..1MBQ7vqISX2YjjusJs17MZuvKuJsYvsL7YBE7LY. .... idLi777ijQ u1YP:iBYsuJL77EKqUrLYsYJsJssY.X5XK iX
                                :                    .:XgQQUrqSS5XjjsujjLSY2gPvIqYsjLYv7YEQUr777...iriSdr7r7riPP v1u5i PbYsuvvrbb1K77JssYjsjssr2gSqj d
                                .                   .i2ZBRZiPKS5XS1suJjYJKLEg2Yb5YuYLvvLPZB7rr77vrvLv7gUrr7rrrQr LXYS:..djJssv7IgsZu7YjYjsusuL7uBqPP:iJ
                               :.                   isZgQQvubSIS5KjJJjsYPSJRb1uZLsYY7v7SqqIri7r77777isgvi7rr:jRi.71LU:..iSLjYvr1QuPR7sJjsuJujj77MgbZU.S
                               r                   ivMUjBqrdX255S5JJ1JY1QsPMKjKS7vY7rrIPX.UirrrrrrrriSXrrrrriPZ. i1v2.:..JuLs77sBU2Q5vJJjsuJuJLrPMZZq:r.
                               r                  .LbQ DQLJZ2SIS5SsXjJvgEJgDUjq1rv77iUKb.iXrirrrirrivqsirrrrrEY. rYYY.::.ruvvvvJQquMEvsujuJus1L7UBdgKJ:.
                               i                  LIB: QZiPX5ISIS2IKs7PMS2RPjLEvr77r1Kdi vXiriririr:Id2:rii:Lqi .iU1L:i:::ULvvrvBEUdQLYJus1JujJ7JZgZq27.
                               r                 ijBP .B77ZS25ISI5qq7jMduPgXvuP7r7ruqqv  J2iiriririvdE7irrirI1.  iYu:..:..7u7jivQR2PQ2vjJuJuj1uvs5PRKILi
                               i.                JEB. 7BiUZ25IX552DI7qB22EDUY2di7rvLKU.. sIiri7rriiXjrririisEi   iUv....:.:j7YirvBqXBKvJ1JjJ1jULv5bMbU1i.
                                .               :PBU  1B:bP5I525IXDuJEguSRPuLUv7r1:sK:.: U1iir7riisY.7iriirP2    rU: .     7vJ:: bgqMd7u1jsuJuUJigQQP5U:.
                                                5gB   qE:DP2S25I2KMYIYPjIMbs5:rvs7:Xv....jXiirsii7s..vririqE:    vr ..iiri.:v. :.:QEgdvJ2suJuJI1iERgDIjS .
                                               .ZB1   QIigXSIII51ZEjL:P2jgqUU.ijv.:I:::..vKr:s7i7s..:virrvKv     77qDQBBBBQDq:  . LQZg7UUssuJJ2X:Z7qgXLR: .
                                               :QB    PY7g5IX2S25ZE2:.DuXbLXi :Ji ri..:. 7P7rur77:..77rrj:u     UBg1RBBBBQBZRBgi. .PQgr22vsYjsSXrj:KMKjEP r
                                               LQP  . jsYQIS5522XgZS.iD2E7L5.. :..:: ..  7Pj1U7r.. .v775: .    L5:.gBBBBBBQBQ1QBP. rQMrbYvvJYJ55iviQgbsIQ  :
                                               jB:  i Jj5g5IS2IjbDQJ rQ5u.Pr  75SI5UL7.   PXLLr.   :Jj7i      .. .BBRggdDbZgBE:DBQ. ggvB77YLsYKYivPDQKYuBi :
                                              .qB  r  rSPQ255IuIZggr rQq:.U :QBEQBBBQBQS: rK.r.    iY.           EBjrLDQggZggBv.DBM iq2Br7vYLJbL7dKEM5YURg  .
                                              .M1  r  rqbDS2qUUXgZg: iBS. iUBd:dBBBBBQBZJ. i                    :B:.JBQZMMRDMBR.:EBu.7QPr7YLYsDIggUZMuuuBQ2.
                                     . . .    .Q. i.  :ZKZI5PI1ddZBi :B7 .gB1 DBQBRRDMQBB7                      .   iUKXKZgDsQg ::ZD7sBJrLvL75ggRdsgM2jUQBB5r.
                                    .        ..Z  L   .ZPEPUE1SddPBP .R: qB1 sBBPPggRgMgBB:                     uBRgPYvvPI2XSi. ::PJ2iD7vvLvLbMdPdJggS1SBSgQuj.
                                             ..1 i:    bdEP1dXSEPbMB7 r.iBd. BBvvDRgSEgRgEZ                     PB7.    . :JqB.  i .L.SL7Yv7IgEqPgUMEPjdB7 QEUX
                                             ..: Y.    vQPdjZPKddPRDQ:  UBv. BP .qPES1qgBEP.                    :D  ...    .Pg     ::ibvLv7YQMdSbEPgDdIdBi  Q5I2
                                             :.. 1     .BdEXXDPEPPgZgZ  qBv. .  .JiXDUiJvvBB                     vJ.   ... .2.       PSLv7vRggqPPDZDEZqgMi   Rjq:
                          .   . .            .. i7  .   QDqbSEZdEPgZPRJ vMP   DBBEXL:. .   J                      ::    :i7:    .   rDU77vDdgSPXDMDERdbQg..  .Rur
                         .                   :. 7:      qB5dbbbEPbdEqbQv .Y    BBXs   .  ..:          ..             .......   ...  KXL7ugPPDSXdgBDMX7SBX     7Qr:
                                             .:.1.      IBXEQqdddPEEbqZBv .     idY  .    :           ..             .......:.:..  YXsvSMdb1d5uDBgKLr7gB7 i    PP :
                         .                   .::R       7BqdXgDEbEPZPPPB2..       ii::.. .                           ............ rILsXEPZK125IMXL77r5RBr i     B...
                                              r.B.      7BZYPZQgdPddEPgZ .:.       ::...... .                         .........  iq1jIPKDbK1SPXv7vY7vqBQj..     sL .
                                              ..22      7BU1ZdbMDEddddQ7  ::  . ............                             . . .  vD7XPPXEEE5Kb27vLsv7jZQgs. .     U :
                          .                    :iBr     SR7EqddEgEZdEERdr  :. ..:.:........                                   :uS. PdqDdbEZPJ7YYsYLvPQZE1i       ii.
                                               ..5BY   iDLjbudbddEdEdgEdQRI5v  ..:...... .          .i7JJ1uUjY:            . .:.  7QPDPKRQKv7sLsYs7uQEKDLZ.       7.
                            .                    :ZRbi7qs7X5IbqPZbEdDbPPPEgKZL  .......           .J5Yr:....:r5Y                 :BbZP5RQU77sLJsu7:ZMSPbvEZ .     v.
                                                  iMggKsvuSS5SKDEZdbPPSKKgKKSMs    .             :Ps:. ..... ..7.               :BgdPPgMs7vsYjj27.KBKqqP7YB :.    I.
                              .        ..      .:r2s.rsvYXXII5DEgDK5DKqKDdKKPPBU                 .s..............              rBgdEdgML7vYYu22i uBEEKd5v7R. .    X
                                       ........i:rr iXvsIK5IUdERDXJgPPqdgPKPKPdBP                  .............              SBDgg5qQY7vssIU7. 7BZ7ugP1vvXr :   J.
                                                .: iQ5v1KS5UqDQdIsbEbELPDqPKPKPPBR                  ..........              7BBbMgL1Bs7LJs5L.  vBZg1:BPLvv1:.r  :.
                             .                 :: .QSvYUSX25RgussXggR:uRqqPPqPqPPQB:                   . .                rQBgPMZrsBu7vjJIr   uBgPMD Q2v7Y2 .r
                          .                   .r .7u77v1q2IgbrsUIMQR :BEXqdqPKqKPPgQP.                                 .uQBgdqQqrvQs7LJJs:.::5BRd5Bg K57vY2 i:
                     . . .                    i ::Yj7v7IIdM1iY22gBM  BDbUddPKPXPKPPEQBgL.                           .JBBRgPPqQXrrBi:JJYi:rYrXRMMSvdE 12vvKr 7r
                    .                        :.. :dvv7jSbg27v22dBQ  bgMSIEgqPqqXqKPqbbMBBg5i.                    .iLs:bQPKPKRSirQK 7jYvrjLrqggRqd.Qi 1UL2P  u:
                                             ..  LSL7vPg:ss2LS5BR  .BdZ2UDEbSqXqXPKqKPKPdgQBBBDQRI:.          .i7sr:. vQSqXMPirgB.rusJYu77EMgQP5 .Q  PIqX  .b
                                             ..  :1LvKg i2K221BB   jBqP1IdgPqXKKPXqKPKqKPqPqEdEBBvir7r7iri:.irvri:... UBDqDgrrgQu.1YsLLsbBBBBbPi EI 7gr   .J.
                                             .   .2L2Z  XuKIUXB:   bZq5I2EZEKqSddqqPKPKPPdgQgqPB1 .:iiiiirrrii::..... vBQq2u7QQBirJJLvED1vri. .Bu2BLv     :
                .                           ..   :Sug  .P1qU2Q5    dgXX5SPMDEqPQMqPPPPgDBQZr IBQ7 ..::::i:i::......  .SDB5JLbQDb:ssvvBE        rB BP
                                            :.   :Xq.  .d2KXXBJ    dBRMRgQQBBBgBBBQQRBBg7.  :B1Q: .......:....... .:7SSgDEub   urJ7vQK  .. ...  Q.IB.i
                .                           ..    q7    QEggBBP .. :ji7:ii7rir:iv77rLI:     bEuIP:  ......... ..irsu1UMgg2Zi   gsrLQL   ......  ZiLB.:
                 .                           .    ir    LM1v:.                             :Qq2UIds:.. .  ..ivvjJjYJ1gggBB1   iB7LBJ           1B.BB
                                                  .r.                             . .     .QBu55S1I12vi:rLssULvvYsJ5QRQQBB.   LQYgK           iQiBB .i
                                      .....i7IbQBQgRQQKv:..                      ...      iBRU1SXXI5UII5I2u1j1JUjUqQQQZB:2.   7BPR           vU KB .JPi
                                      .:rr7r7ii::..:rYPMKSP1jvv7r.               ..       :QBdUuKdP25U2U225U52I1XDBDKXBi .:   .BB.          us.jr ivi.:
                                           ...            .:rIvi:vv.             ..       .BQRDPu2ZMPqI2UU1U2PdRgZUuPB7   :    BE         .Ui.v:.i.  .::
                                              . . . . .  .7:  .sY..jr            ..        BBgMMgK1XRQMEdPZgQQgqUs5BBi         BY        :j.:r:.. . .:.:.
                                       ..........i::... igggPs. :2r iu           ...       DBQggMQD21MQMRQQQb2YJ2gBB:          vs       7r.i::.  . .:. .:
                      .         ....:::::::.:::...::i:::DIYvXEgs  7J..U:      ..  ...      7BdQgggQMSjZMMdP1JsSdQBB:            Z     iv::i:.   . .:. . i
                           ....:::.:.................. :ii:i..:s1r :U: si    .      ..     .BU5QDggggEU2jJLJ5DMQQB7             .:  :s7:i::.  .. ... .  ::   .
                        ..:.:........................ :i:ir.     .i .uv rv                  ZB1IMDgDggMP2uKZQMMRBK                iLrii:.:. ....... ... .i
                     ..:.:.......................... .7ir: .       :. vu.:Ii                rBQK5ggMgggQRQQQgMRBR               :Li:i:.i:  ....... . ... r     .
                  ..:............................... r7:.  .. . ... :: iX: J1               .BBBgdRRBBBBBBQQQMRE. .           i7i:7i.rLi  ... ....... .  i.     .
                ................................... .U:.   ... ..... :r :b7 id:              gBBBBBQMgEDRBBBQgE.            isi:7r.i2vi. . . ....... . . i.        . .     .
              ..................................... vY  . .  .. ...   rs..qS. Pj        .    iY:.          .:rv:7i.      .UJriY7..IIi:i . . .r. ........ :i                 .
            ........................................I: ... . ... ...  .r5. Ydi 7D7     ...                      .::rv7:vQBuuBP..sPv::r.  .  v. . ... ... .i                  .
          ........... ... ...............   ........v ..... . ... ...  iiIi .Dg:.Pgi...                              .:1Z1BBr.jPSr::ir. .  7r   ..... ....r
         ........... ..... ..............JK7 ..... ii  ....... ... .   i::uX::QB5...                     . .              :.vQg2i::iir .. :u   . . . ... .r
       ...... . . . ..... ...............dBM: .... 7i ... :.:.. ... .. .r::vE7..                                             .vLLrri7r   :P:  . . ....... r
      ...... ... ... . . ... ........... :ggS  ... J......::.:.  .:. . .rrr:.                                                  .iuYr7r  .5v  .............7                  .
     :....... . . . . . . . . ........... 1DM: ....L......:...:.  .Y. . ri.                                             .   .     ruL: .Ss: ..............7
    :: ..... . .     . . . ... .......... .DgK ....u......::.:.:.  7U. .                                             .     .       .5r 5v7 ............. .r
   .i ... . . .       . . ................ rQMr ...K: ....:.:.:.:. .5U.                                               . . . . . .    7Pr7. .......... ....r               .
   7 ... . . . . .:.   . .................  2Bb .. 5: ...:::::.:::.:v.     . . .                             .r7v.     . .   . .      idi  ......... :7J.:i              .
  7:  . . . . .  rgX.  .................... .J: ...7i ...::::.::::vi    . .                                  YgSZ7    . . . . .        .K  .......  :vL7 i:
  v  . ... . . . .Xqq.  .....................  ... 1i ...::::::::7:        .     :vq:                  .     iKjUu     . . . . .        .P. .... ..777L. 7.
 ii ... . . . . . .qPP. ...........................qY ...:i:::::7.    .   .     :ZXIX                        :PYU2  .   . . . .          ib     :7Lr7vi .u.                 . .
 v.... . . . ....  :qbS  ........................ rEI. ..::::::7.  . . . . .    .djJX7                       :PjuK     . . . . . . .     .v5 .ivv7rr77  75
:r .. ... . .....   :qQX ........................ qsP: ..:i::.Y:    . .          25YJK      .       . .      :ZJ1d  . . . . . . ....     ..JSrvr7rr7L  rvu                            .
Yr ................. .17 ....................... iqi5r ...:i.7s  . . . . . . .   :EjYKL    . . .     . . .   :DIUg   . . . ... . ...   ..::.Pj:iir7L. iLr5
Z:. .................   ........................ r1:Sj .. .::d.   . .   .     .   UKjJg.  .   . . . . . .     DZMU  . . ... .......    .::::iqvLi7v. .Yr7U
R............................................... LYiuP  ... rU   . . . .     . .   EKIbE   . . .   . . . .     .:    ..... . ... . .    .::i:uiLPr   :vrrL                               .
Q.:............................................. 7J:JEr ... 1:  . . . . . . . .    .REXL  . . . . . . . . .       . . ... . . ... .      :vIsi2 :i   :Yr7s                                .
Q............................................... ru:vP2  ...d    . . . .   . . . .   .     . . . . . . . . . .   . . ..... ... .     . ..Jb7  Qi :i  .v7rI                               .
R::...............................................d:L5d:   .g   . . . . . . . . . .     . . . ... . . . . . . ... . . . . .        .UEqjKv   .Q7 .u . :L7j                                .
Xr::............................................. dr7XSX   :d.   . . . ... . . . . . . . . ....... . ... . ... ... ... .     ... :PPi.:1dXr. jJ7 .u .. isj                             .
rv:::............................................ Ivi2SP7  :Z.. . . . . . . . . . . . . ......... . . ... ... . . ... .  .:ii::.  :vPU:  :KXIJr: .2 ... vj      . .
 U:i:............................................ 7U:r2EEr .Q..    . . . ... . ..... . ..... ... . . . ... . ..... . . .ir.          rEP:  :UqXL .P. .. :I .:i:i:::::.........
 JL:ii:.......................................... ivrirYEQY Q:.   . . . . ....... ... . ....... . . . ....... . .      v.r7i:.         LMX.  rPqr.::. . v7....................:...
 .P:ii::.....................................:::::r7iririvZKBv:.   . . ....... . . . . ......... . . ..........       ILYIr7LsLi        .2gY  :q55  7.  j. ......................:::.
  Dr::i:i:..................................::::i:rvrr7i  .7QP::.   . . ..... ... . ... . . ... . . . ..... .    .r7SKq7:  .iirrYr        iDP. .XS: J  iq ..........................:i:
  iZ:iii:::................................:.::i:i:Ji77. .  iBii:    . . . ... ... . ... ... . . . . ... .    .rY1Ys7i.  .  .iiri7jr       .XE: i5JPi iIv ............................:r:
   KJ:iii:i:..............................:::::iii:Yrri....  Ij:i.  . ... . . . . ..... . . . . . ... .    .i7Yri::.. . ... ..::rirs5:       2b7 v1Xr.7Ui ..............................:i:
    gr:iiiii:............................::::iiii:iRLii. .. r.vri:         . . . . . . . .               :iri.     ......... ..  .  .Li      iI5i.LZQY:S......   .........................:r.
    .Dr:iiiiiii:::....................::iiiiriiri:rbQiri  . u .1Y7.i:                                 :iri.     . ... ....... . .     vi   .. 7UI iBBXiL .... .::...........................ri
     .Pv:iiiiririri:::.:...........::iirrrr777ri.:. ggJv:   :J :ZY ..::v1r..           ...:i7JLY7vjXdb7:   . . . ................... .77  .:..:S2. BBXrr ...  75U. ..........................i7
       22iiiririiirii:i::::.:.::::iiiirir7vri..   v  iKPS:   rr .K  .uQq: :gPr::i::ir7Lj2jusv7sss2QB2   . . . ..... . . ........... .irr: :....vZ: QBYr..... 7dK7 ............................:v.
        iIvriririiiiiriiiiii:iiiiririr7vr:        ri   :LKr.  r:  7KPX:  su: iKZjusY7r:....:irirvL.    . . . ... . . ... . .....   .ii:rv..:.. 1B. BB7s ... iZPq ...............................7.
          rvL77rriiiiirrrirrrrrir7v7r::            P.    .ii.. r rBBB..Lu:    .r.     .:i77r::ir.     . . ... . ..... . ... . .   .ii:::1..... BB .BB.7:....PPd. ................................v.
            .:r77777r7rrr7r77Lvs7r..               Xv. ...  .. .YBZ2. 77..       ..i7sY7i: .:r:    ... . . ... . ... ... .....  .:ii::.:b....  BU gB: .7.. SZD: ..................................L.
                 ..:iirrrrrii..         .          2J7. .........    .:..   ..irsjj7i..   .::   ......... ... ..... .......   ..:::.::.PB ... JB  B5 .2...iZPi ...................  ...............U
                                         .   . .   2s7r. ... . . ... .    .rJUuvi:.. ...::................................  .irii77Lss5BB .:  Bg BR  Ei..........:.:............. iSr..:.:.........iJ
                                                   :u.::. . ...           .:..         ::                                 .:rii7u12j7L:.Y .  PB.rj  rK. ... . ...................vDq. ............. r:
*/
#include<bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define ULL ull
#define mp make_pair
#define pii pair<int,int>
#define piii pair<int, pii >
#define pll pair <ll,ll>
#define pb push_back
#define big 20160116
#define INF 2147483647
#define pq priority_queue
#define rank rk124232
#define y1 y20160116
#define y0 y20160110
#define _ 0
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
namespace Mymath{
	LL qp(LL x,LL p,LL mod){
		LL ans=1;
		while (p){
			if (p&1) ans=ans*x%mod;
			x=x*x%mod;
			p>>=1;
		}
		return ans;
	}
	LL inv(LL x,LL mod){
		return qp(x,mod-2,mod);
	}
	LL C(LL N,LL K,LL fact[],LL mod){
		return fact[N]*inv(fact[K],mod)%mod*inv(fact[N-K],mod)%mod;
	}
	template <typename Tp> Tp gcd(Tp A,Tp B){
		if (B==0) return A;
		return gcd(B,A%B);
	}
	template <typename Tp> Tp lcm(Tp A,Tp B){
		return A*B/gcd(A,B);
	}
};
namespace fwt{
	using namespace Mymath;
	void FWT(int a[],int n,LL mod)
	{
	    for(int d=1;d<n;d<<=1)
	        for(int m=d<<1,i=0;i<n;i+=m)
	            for(int j=0;j<d;j++)
	            {
	                int x=a[i+j],y=a[i+j+d];
	                a[i+j]=(x+y)%mod,a[i+j+d]=(x-y+mod)%mod;
	                //xor:a[i+j]=x+y,a[i+j+d]=x-y;
	                //and:a[i+j]=x+y;
	                //or:a[i+j+d]=x+y;
	            }
	}

	void UFWT(int a[],int n,LL mod)
	{
		LL rev=inv(2,mod);
	    for(int d=1;d<n;d<<=1)
	        for(int m=d<<1,i=0;i<n;i+=m)
	            for(int j=0;j<d;j++)
	            {
	                int x=a[i+j],y=a[i+j+d];
	                a[i+j]=1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod;
	                //xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;
	                //and:a[i+j]=x-y;
	                //or:a[i+j+d]=y-x;
	            }
	}
	void solve(int a[],int b[],int n,LL mod)
	{
	    FWT(a,n,mod);
	    FWT(b,n,mod);
	    for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%mod;
	    UFWT(a,n,mod);
	}
};
namespace Maxflow{
	const int Maxn=1005;
	struct edge{
		int to,rev,cap;
		edge(int _to,int _rev,int _cap){
			to=_to,rev=_rev,cap=_cap;
		}
	};
	int src=1002,snk=1003;
	vector<edge> G[Maxn];
	int dist[Maxn],seen[Maxn];
	int n;
	void Clear(){
		for (int i=0;i<Maxn;i++) G[i].clear();
	}
	void bfs(int s){
		for (int i=0;i<Maxn;i++) dist[i]=-1;
		dist[s]=0;
		queue<int> Q;
		Q.push(s);
		while (!Q.empty()){
			int x=Q.front();
			Q.pop();
			for (int i=0;i<G[x].size();i++){
				edge &e=G[x][i];
				if (e.cap && dist[e.to]==-1){
					dist[e.to]=dist[x]+1;
					Q.push(e.to);
				}
			}
		}
	}
	int dfs(int now,int dest,int fl){
		if (now==dest) return fl;
		for (int &i=seen[now];i<G[now].size();i++){
			edge &ed=G[now][i];
			if (ed.cap && dist[ed.to]==dist[now]+1){
				int f=dfs(ed.to,dest,min(fl,ed.cap));
				if (f){
					ed.cap-=f;
					G[ed.to][ed.rev].cap+=f;
					return f;
				}
			}
		}
		return 0;
	}
	int dinic(int s=src,int t=snk){
		int ret=0;
		while (1){
			memset(seen,0,sizeof(seen));
			bfs(s);
			if (dist[t]==-1) return ret;
			int f=dfs(s,t,INF);
			while(f){
				ret+=f;
				f=dfs(s,t,INF);
			}
		}
	}
};
namespace Geometry{
	struct iP{
		LL x,y;
		iP(LL _x,LL _y){
			x=_x,y=_y;
		}
		iP(){
			x=y=0;
		}
		iP operator +(iP p){
			return iP(x+p.x,y+p.y);
		}
		iP operator -(iP p){
			return iP(x-p.x,y-p.y);
		}
		iP operator *(LL k){
			return iP(x*k,y*k);
		}
		LL det(iP p){
			return x*p.y-y*p.x;
		}
		LL dot(iP p){
			return x*p.x+y*p.y;
		}
		LL dist(){
			return x*x+y*y;
		}
		bool operator <(const iP &p)const{
			if (x!=p.x) return x<p.x;
			return y<p.y;
		}
	};
	struct dP{
		double x,y;
		dP(double _x,double _y){
			x=_x,y=_y;
		}
		dP(){
			x=y=0.0;
		}
		dP operator +(dP p){
			return dP(x+p.x,y+p.y);
		}
		dP operator -(dP p){
			return dP(x-p.x,y-p.y);
		}
		dP operator *(double k){
			return dP(x*k,y*k);
		}
		double det(dP p){
			return x*p.y-y*p.x;
		}
		double dot(dP p){
			return x*p.x+y*p.y;
		}
		double dist(){
			return x*x+y*y;
		}
		bool operator <(const dP &p)const{
			if (x!=p.x) return x<p.x;
			return y<p.y;
		}
	};
	vector<iP> convex_hull(iP X[],int l){
		#define sz ret.size()
		vector<iP> ret;
		sort(X+1,X+1+l);
		ret.pb(X[1]);
		for (int i=2;i<=l;i++){
			while (sz>=2 && (ret[sz-2]-X[i]).det(ret[sz-1]-X[i])>=0){
				ret.pop_back();
			}
			ret.pb(X[i]);
		}
		int rs=ret.size()+1;
		for (int i=l-1;i>=1;i--){
			while (sz>=rs && (ret[sz-2]-X[i]).det(ret[sz-1]-X[i])>=0){
				ret.pop_back();
			}
			ret.pb(X[i]);
		}
		return ret;
	}
};
const int Maxn=200005;
int a[Maxn],n,b[Maxn],c[Maxn];
int bit[Maxn];
void add(int x){
	while (x<Maxn){
		bit[x]++;x+=x&-x;
	}
}
int query(int x){
	int ret=0;
	while (x){
		ret+=bit[x];x=x&(x-1);
	}
	return ret;
}
bool check(int x){
	for (int i=1;i<=n;i++){
		if (a[i]>=x) b[i]=1;
		else b[i]=-1;
	}
	b[0]=100000;
	for (int i=1;i<=n;i++) b[i]+=b[i-1];
	memset(bit,0,sizeof(bit));
	add(b[0]);
	LL tot=0;
	LL al=1ll*n*(n+1)/2;
	for (int i=1;i<=n;i++){
		tot+=query(b[i]);
		if (tot*2>=al){
			return true;
		}
		add(b[i]);
	}
	//cout<<tot<<endl;
	
	
	return false;
}
int main(){
	n=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<=n;i++) c[i]=a[i];
	sort(c+1,c+1+n);
	int lo=1,hi=n+1;
	while (hi-lo>1){
		int mid=lo+hi>>1;
		if (check(c[mid])){
			lo=mid;
		}
		else{
			hi=mid;
		}
	}
	printf("%d\n",c[lo]);
	return ~~(0^_^0);
}




Measured memory_bytes: 2176