CT58992

Granite beacons Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Ishaan inherited the observatory at the bamboo terraces of Verdantstep along with its curious bookkeeping system for beacons. Time to make sense of it. 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: 3237 941914281 991210002 -85206846 958916614 -415659341 -650692288 966484463 990499373 -480371602 -617056778 -987338518 -190334465 -790807543 292034057 -875735629 -33089955 735181315 -486433142 858505754 196239561 915415669 -957929795 701644107 -305145543 984635772 -230774973 -896627168 -81053809 -900258601 -128122694 -687910634 -51662549 -588332587 642879134 628285422 958227633 780897689 545482932 737540349 -583010816 353999801 318056282 468476764 795283247 846738793 5742370 -316490415 968501630 -432338828 36799321 -445263611 459465708 288506496 218024092 129887041 534776407 -429549045 578732630 -862894227 -906040805 -720407886 -215071621 -895440193 7412627 -458523397 -672054324 402049778 629081158 -526166716 -352218218 220180829 810770175 -666181635 -34875195 626302352 -796312588 -601670…
Output: 941914281 941914281 941914281 941914281 941914281 -85206846 941914281 941914281 941914281 -85206846 -85206846 -190334465 -190334465 -190334465 -190334465 -190334465 -85206846 -190334465 -85206846 -85206846 -33089955 -85206846 -33089955 -85206846 -33089955 -85206846 -85206846 -85206846 -85206846 -128122694 -128122694 -128122694 -128122694 -128122694 -85206846 -85206846 -81053809 -81053809 -51662549 -81053809 -51662549 -51662549 -33089955 -33089955 196239561 5742370 5742370 5742370 5742370 5742370 5742370 5742370 36799321 36799321 129887041 129887041 129887041 129887041 129887041 36799321 36799321 5742370 5742370 5742370 5742370 -33089955 5742370 5742370 5742370 -33089955 5742370 5742370 5742370 -33089955 5742370 -33089955 -33089955 -34875195 -33089955 -33089955 5742370 -33089955 5742370 574…

Example 2:

Input: 3454 -801666920 351506853 -758659628 902435674 -383386406 750473146 -860293716 809292847 455881081 -277796695 -142098410 67603555 -836620700 631153963 24994720 208244708 825746542 62105246 -703680673 -962082621 877321417 -871087994 -449982908 -554322575 484187117 -349429690 698785361 -459795050 671970967 619214297 -182708051 -525115623 -302750301 -40482443 196151205 -186789751 -48139701 -127688476 807199415 253426923 -218751217 312686410 -910936106 -573699502 -766243131 -631154181 -665668604 -217301899 357394377 -200293592 -816618186 339544080 -498638066 270159078 -173841253 52433513 916083999 -773914297 -199532 48935230 272666370 -575541815 -169117207 505390810 -512826736 -533624371 -234738259 190696504 722094544 -738924335 -580264133 18876701 -312667495 671079261 -963321114 -864086850 91…
Output: -801666920 -801666920 -758659628 -758659628 -383386406 -383386406 -383386406 -383386406 351506853 -277796695 -142098410 -142098410 -142098410 -142098410 24994720 24994720 67603555 62105246 62105246 24994720 62105246 24994720 24994720 -142098410 24994720 -142098410 24994720 -142098410 24994720 24994720 24994720 -142098410 -142098410 -142098410 -40482443 -142098410 -48139701 -127688476 -48139701 -48139701 -48139701 -48139701 -48139701 -127688476 -127688476 -142098410 -142098410 -182708051 -142098410 -182708051 -182708051 -182708051 -182708051 -182708051 -173841253 -173841253 -142098410 -173841253 -142098410 -142098410 -127688476 -142098410 -142098410 -142098410 -142098410 -169117207 -169117207 -169117207 -142098410 -169117207 -169117207 -169117207 -169117207 -169117207 -169117207 -173841253 …

Example 3:

Input: 699 91660606 374079061 993346763 -696723692 -72499236 -690689211 -986317517 -823251364 846170366 -293153653 734167329 -206285157 -85386336 80447853 623818565 632535146 -446748092 372170719 -161273312 -672523728 728336114 -150877268 460705290 -174318909 654494171 -556023550 -887631576 -966724502 -278577390 -238022247 -250146951 -876074049 -631156555 877773494 161297433 805054398 -767987275 -575781088 175435222 -35844845 749485252 998378668 -468662769 -52224743 211883697 92904468 -21610705 453446822 42337246 -765027844 -405484448 -182996180 -331271998 -692791552 -739389098 687297474 970397048 264134794 599528843 196858926 727242959 886711993 856784869 47155529 210269851 699825478 -960285180 -269093522 808499697 232650099 400504473 -36478454 276518234 -967947947 -347821786 411123070 -13966586…
Output: 91660606 91660606 374079061 91660606 91660606 -72499236 -72499236 -690689211 -72499236 -293153653 -72499236 -206285157 -85386336 -85386336 -72499236 -72499236 -72499236 -72499236 -72499236 -85386336 -72499236 -85386336 -72499236 -85386336 -72499236 -85386336 -85386336 -150877268 -150877268 -161273312 -161273312 -174318909 -174318909 -174318909 -161273312 -161273312 -161273312 -174318909 -161273312 -161273312 -150877268 -150877268 -150877268 -150877268 -85386336 -85386336 -72499236 -72499236 -52224743 -72499236 -72499236 -85386336 -85386336 -150877268 -150877268 -150877268 -85386336 -85386336 -72499236 -72499236 -52224743 -52224743 -35844845 -35844845 -21610705 -21610705 -21610705 -35844845 -21610705 -21610705 42337246 -21610705 42337246 -21610705 -21610705 -21610705 -21610705 -35844845 -35…

Constraints:

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

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