CT61363

Moonlit marks Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the kelp forests of Tangledeep, Jatin records each marks in a worn leather ledger. The guild wants answers, not guesses. 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: 835 541868389 -578864080 -964205827 262404518 -796413348 619751778 -533987566 -466473696 161333546 -714915158 -715160883 261494290 -337823548 -110296788 -244448073 999142497 -576467018 -504805652 802939311 -364077986 -166963272 -333228845 -42267215 -639897120 42572173 108578620 37762959 -818426777 -795967679 -608308440 -589506541 210783079 -397472826 -111136044 -78646242 -329451093 -782491509 -986201070 20441755 -333722838 -951469459 701507917 -88537541 -355855649 -832395485 469181445 -537922639 -505055141 -564014662 -565283152 509110840 581173211 -949054079 -742126797 633044181 564913467 567118986 421257932 609826736 -130232481 497353663 923423994 853123922 527087162 762803901 26327545 -16692644 -256375232 688535102 -561161156 -370698184 -315548467 -170682068 598010819 -118343801 -8194917…
Output: 541868389 -578864080 -578864080 -578864080 -578864080 -578864080 -533987566 -533987566 -466473696 -533987566 -533987566 -533987566 -466473696 -466473696 -337823548 -337823548 -337823548 -466473696 -337823548 -364077986 -337823548 -337823548 -333228845 -337823548 -333228845 -333228845 -244448073 -333228845 -333228845 -337823548 -337823548 -337823548 -337823548 -337823548 -333228845 -333228845 -333228845 -337823548 -333228845 -333722838 -333722838 -333722838 -333228845 -333722838 -333722838 -333722838 -333722838 -337823548 -337823548 -355855649 -337823548 -337823548 -337823548 -355855649 -337823548 -337823548 -333722838 -333722838 -333228845 -333228845 -329451093 -329451093 -244448073 -244448073 -166963272 -166963272 -130232481 -166963272 -130232481 -166963272 -166963272 -244448073 -17068206…

Example 2:

Input: 903 459369138 685067188 3544759 -625015794 -874650761 850706825 785386939 -607818854 387073150 -424351509 774203679 -268543305 -972993681 -626710947 -168254413 939851757 594825779 865508191 -499632450 -532750622 387985184 780196242 -935326125 -739553356 71063253 946838293 -40186591 -513465059 413585768 -742064731 781531023 -534305078 -35126338 -827926307 252436216 -613030715 -998900541 -671279174 74176241 -143852820 -430355035 -655269507 -386681742 36927164 607505802 -911112618 -169784921 -324475342 -361713564 -46039960 -305496695 440128009 810716299 569275646 -565607501 -444440973 593561714 -785577318 -496088536 -778300632 308872094 -388454495 836862431 -38603900 723233031 -164283996 735875679 -302425745 -812088480 -509308671 -976621301 -468134170 409805338 306526349 -195259586 -324413424…
Output: 459369138 459369138 459369138 3544759 3544759 3544759 459369138 3544759 387073150 3544759 387073150 3544759 3544759 -268543305 -168254413 -168254413 3544759 3544759 3544759 -168254413 3544759 3544759 3544759 -168254413 3544759 3544759 3544759 -40186591 3544759 -40186591 3544759 -40186591 -35126338 -40186591 -35126338 -40186591 -40186591 -168254413 -40186591 -143852820 -143852820 -168254413 -168254413 -168254413 -143852820 -168254413 -168254413 -169784921 -169784921 -169784921 -169784921 -169784921 -168254413 -168254413 -168254413 -169784921 -168254413 -169784921 -169784921 -268543305 -169784921 -268543305 -169784921 -169784921 -168254413 -168254413 -164283996 -168254413 -168254413 -169784921 -169784921 -268543305 -169784921 -169784921 -169784921 -195259586 -169784921 -169784921 -168254413 …

Example 3:

Input: 2615 -225720758 -889364496 60897580 90788303 882296616 789494834 -109376355 -779100468 11834848 -51711822 275823306 -988051359 775750602 691528374 -169576015 672862091 -925890662 -155641599 -572473157 -586330023 -60946148 -359460190 -342976625 -772144947 -21011268 773028625 92097967 657412305 869102980 728268340 455398740 2755469 -53304616 612645648 507002846 -687205139 -715135737 -852884912 -50994617 90792846 -929148448 -786132035 446617083 948337104 881885534 -909169222 231530171 552337814 371029754 575753486 -266175902 56158131 -161309111 -855639147 -338136459 -419779897 -628456649 751866596 856841104 -949570095 340087728 -73907546 -526973626 -822701269 -634470441 -415913508 481742571 238850244 500213263 856200844 -948464461 155212294 -521441928 -642378679 244494903 -232476742 344492486…
Output: -225720758 -889364496 -225720758 -225720758 60897580 60897580 60897580 -109376355 11834848 -51711822 11834848 -51711822 11834848 11834848 11834848 11834848 11834848 -51711822 -51711822 -109376355 -60946148 -109376355 -109376355 -155641599 -109376355 -109376355 -60946148 -60946148 -51711822 -51711822 -21011268 -21011268 -21011268 -21011268 2755469 -21011268 -21011268 -51711822 -50994617 -50994617 -50994617 -51711822 -50994617 -50994617 -21011268 -50994617 -21011268 -21011268 2755469 2755469 2755469 2755469 2755469 -21011268 -21011268 -50994617 -50994617 -50994617 -21011268 -50994617 -21011268 -50994617 -50994617 -51711822 -51711822 -53304616 -51711822 -51711822 -50994617 -50994617 -50994617 -50994617 -50994617 -51711822 -50994617 -51711822 -50994617 -50994617 -50994617 -50994617 -50994617 -…

Constraints:

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

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