CT60605

Nandini's Middle So Far Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The reckoner Nandini has been asked to prepare the expedition manifest. On the desk lies a long table of marks readings. Task: After each arrival, print the median of the stream so far — defined as the element at sorted position ceil(k/2) (1-based). Input format: First line: n. Second line: n integers. Output format: Print n medians space-separated. Constraints: 1 <= n <= 4000; -10^9 <= a[i] <= 10^9.

Example 1:

Input: 1548 733298366 585928724 -764811797 -654078971 344898056 -854813971 465011483 67718687 568986142 545652414 -452429078 -308492147 -403412818 943573227 -488710237 -273937510 960855218 512882477 431492507 -799104515 -177178516 -540319959 234546046 756518038 -138656956 734325839 -523682459 -789348875 -654830881 530474706 74916174 245285100 965399721 -178169768 597062969 -958498889 -515410327 -128814839 -454822092 915614218 493197646 666218249 -584936086 274337318 -612485700 470217869 486213036 854431720 -924415922 450018359 912901412 392364024 541867871 -572928261 -188295495 -736032791 -590757746 -900676374 -973635379 -636757768 -261754112 114560583 -506455581 -59080258 772096668 -135813803 -690642924 -673474684 232553206 -159581438 167981656 -970065982 -921230436 666006443 514875519 108449651…
Output: 733298366 585928724 585928724 -654078971 344898056 -654078971 344898056 67718687 344898056 344898056 344898056 67718687 67718687 67718687 67718687 -273937510 67718687 67718687 344898056 67718687 67718687 -177178516 67718687 67718687 67718687 67718687 67718687 -138656956 -138656956 -138656956 67718687 67718687 74916174 67718687 74916174 67718687 67718687 -128814839 -128814839 -128814839 67718687 67718687 67718687 67718687 67718687 67718687 74916174 74916174 74916174 74916174 234546046 234546046 245285100 234546046 234546046 74916174 74916174 67718687 67718687 -128814839 -128814839 -128814839 -128814839 -128814839 -59080258 -128814839 -128814839 -135813803 -128814839 -135813803 -128814839 -135813803 -135813803 -135813803 -128814839 -128814839 -128814839 -135813803 -128814839 -128814839 -5908…

Example 2:

Input: 2925 530257605 497196485 -599499954 -745073409 616323641 -812634161 598476714 -561872395 -880356547 64201930 -949739 -600361293 -796212245 498114431 -476492307 -567998490 -311556930 -648189759 60307808 180550822 463881989 627662984 -4724516 514795863 873710311 87599395 -514084578 -298925870 769319158 -798241329 -39677342 -285797118 -405734680 448093679 -972746999 383976592 -1542960 -620077495 -986108816 -281871317 -120933809 -989665179 -29050827 -268894217 856176388 408088359 106508331 -162636501 273868175 780792003 -663843925 277068074 -802697932 488018837 4765901 -470539588 -15251325 -421388215 -779112971 -567853455 -792364202 -882589924 -376745057 -677344382 -119475355 930385496 333601372 754238894 853991070 -755738171 345140043 -909911034 -189940376 192915493 243983833 -563534964 18550…
Output: 530257605 497196485 497196485 -599499954 497196485 -599499954 497196485 -561872395 -561872395 -561872395 -949739 -561872395 -561872395 -561872395 -476492307 -561872395 -476492307 -561872395 -476492307 -476492307 -311556930 -311556930 -4724516 -4724516 -949739 -949739 -949739 -4724516 -949739 -4724516 -4724516 -39677342 -39677342 -39677342 -39677342 -39677342 -4724516 -39677342 -39677342 -281871317 -120933809 -281871317 -120933809 -268894217 -120933809 -120933809 -39677342 -120933809 -39677342 -39677342 -39677342 -39677342 -39677342 -39677342 -29050827 -39677342 -29050827 -39677342 -39677342 -120933809 -120933809 -162636501 -162636501 -268894217 -162636501 -162636501 -120933809 -120933809 -119475355 -120933809 -119475355 -120933809 -120933809 -120933809 -119475355 -120933809 -119475355 -119…

Example 3:

Input: 1944 318850128 306286443 -914332509 -499425402 -742281490 -227658169 453042396 836337092 771141049 -535682435 147053557 59027417 -483863751 -736790884 789717355 -818997297 474600403 -305253121 -236890368 -619453413 -472552393 868497853 -583572116 956337273 70990396 417102180 -234367323 624348967 -399226695 -128768503 -945996945 -431589101 850796995 841702179 -957558830 -524254413 123056717 485780816 626454865 -693829306 -819461419 -620428300 502437094 77622810 -118451427 286487636 -364728083 493725385 986085692 -628073278 499449646 -712688660 865561760 -363221207 -798932593 -304343929 -558258418 -881816261 -693329192 -577562549 423281291 -809467982 -215569149 -705882782 -116487608 -402809503 -61038967 -21472204 -163508249 207741427 328870466 -622871831 785464702 -158431135 44137254 9363814…
Output: 318850128 306286443 306286443 -499425402 -499425402 -499425402 -227658169 -227658169 306286443 -227658169 147053557 59027417 59027417 -227658169 59027417 -227658169 59027417 -227658169 -227658169 -236890368 -236890368 -236890368 -236890368 -236890368 -227658169 -227658169 -227658169 -227658169 -227658169 -227658169 -227658169 -234367323 -227658169 -227658169 -227658169 -234367323 -227658169 -227658169 -128768503 -227658169 -227658169 -234367323 -227658169 -227658169 -128768503 -128768503 -128768503 -128768503 -118451427 -128768503 -118451427 -128768503 -118451427 -128768503 -128768503 -227658169 -227658169 -234367323 -234367323 -236890368 -234367323 -236890368 -234367323 -236890368 -234367323 -236890368 -234367323 -234367323 -227658169 -227658169 -215569149 -227658169 -215569149 -215569149…

Constraints:

1 <= n <= 4000; -10^9 <= a[i] <= 10^9.

Loading...
Test Cases:No test cases
No test cases available.