CT59120

Nora's Ledger of signals

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the lotus ponds of Tranquil Basin. Nora spreads the signals records across the table and picks up a sharp pencil. 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: 726 131579773 -654868461 383066975 -103341089 763186657 878919741 -27828183 646313153 189074084 -718028235 335427620 -933493797 663105875 452449282 -48556022 435756210 -483564071 285226435 -737342338 -434604652 704914109 -952353966 704885857 700989471 -524456188 -367787986 -143087591 261147916 -348358363 -269477948 738448381 718446404 -233258438 -813420560 800458575 635165170 -459854670 464617139 -991123326 -760214454 -782810517 -324055027 -760077388 696000423 652659735 421186315 553238079 340879303 -781880391 998664470 -52101156 42845625 -265839551 40307374 -816569271 -625175380 292724069 -68406783 267460740 -984228435 888854865 -794802013 -172456000 973843143 -447155216 -475318142 301902181 643531772 -439692948 616757142 1082859 -916482905 812921327 308837698 -436889460 702578368 -701043…
Output: 131579773 -654868461 131579773 -103341089 131579773 131579773 131579773 131579773 189074084 131579773 189074084 131579773 189074084 189074084 189074084 189074084 189074084 189074084 189074084 131579773 189074084 131579773 189074084 189074084 189074084 131579773 131579773 131579773 131579773 -27828183 131579773 131579773 131579773 -27828183 131579773 131579773 131579773 131579773 131579773 -27828183 -27828183 -48556022 -48556022 -48556022 -27828183 -27828183 131579773 131579773 131579773 131579773 131579773 42845625 42845625 40307374 40307374 -27828183 40307374 -27828183 40307374 -27828183 40307374 -27828183 -27828183 -27828183 -27828183 -48556022 -27828183 -27828183 -27828183 -27828183 1082859 -27828183 1082859 1082859 1082859 1082859 1082859 1082859 1082859 -11409944 1082859 -11409944 108…

Example 2:

Input: 327 994861005 -417740222 756583725 -706867447 -884160971 -327442313 -214945199 724596045 120076995 -502936222 780488245 -757568890 -933824356 -139402260 -319516071 841122286 360157207 -333977980 372300993 -503807877 -302858315 -91813814 -157948924 -650435573 -987909333 831384051 -817341457 -564707827 149986193 -487907940 583122483 -138270327 -548089587 -287994845 665730891 -8757314 -657419762 -612387160 -613846453 -132516675 446690356 -641269996 -782241286 520134785 -353428423 -51109625 -946265511 -34540733 -121111092 465303541 828760765 682200225 -551668232 999087085 357494834 634719485 249950252 448905092 -304697720 -297199879 -480092124 -314313973 290813405 894829993 -650833908 163412560 876372017 -738933220 646722535 110622698 -790124118 -360472724 -275141991 633819478 -342484749 -8483…
Output: 994861005 -417740222 756583725 -417740222 -417740222 -417740222 -327442313 -327442313 -214945199 -327442313 -214945199 -327442313 -327442313 -327442313 -319516071 -319516071 -214945199 -319516071 -214945199 -319516071 -302858315 -302858315 -214945199 -302858315 -302858315 -302858315 -302858315 -319516071 -302858315 -319516071 -302858315 -302858315 -302858315 -302858315 -287994845 -287994845 -287994845 -302858315 -302858315 -302858315 -287994845 -302858315 -302858315 -302858315 -302858315 -302858315 -302858315 -302858315 -287994845 -287994845 -214945199 -214945199 -214945199 -214945199 -157948924 -157948924 -139402260 -139402260 -139402260 -157948924 -157948924 -214945199 -157948924 -157948924 -157948924 -157948924 -139402260 -157948924 -139402260 -139402260 -139402260 -157948924 -157948924…

Example 3:

Input: 851 -275951224 -600627752 924401705 -100402889 729186436 -398078855 980288182 -887177767 -81587938 -673010051 966148239 -588961439 -452034896 -586544068 -495927522 10371754 -388321940 975932347 -871862956 703808625 425923019 -851778280 454045751 388074114 350992274 608552638 -485840650 43344227 106762093 694627082 -493288717 895850453 -711167595 -138853005 -199967790 -606476538 -970824891 110211676 808549684 646362961 456671650 684225937 543084594 -685906735 820126103 426840412 -793809968 360417330 -505291575 809882169 -820555842 363701131 978902251 -433925185 -179583706 190044206 -339038356 -16451971 -14088920 623916075 -388949396 -553283569 559498058 -336816654 -460382583 322092786 -422049998 -51048918 -127540726 -829233307 642964780 -844250448 -308456421 281623295 65250990 929478666 711…
Output: -275951224 -600627752 -275951224 -275951224 -100402889 -275951224 -100402889 -275951224 -100402889 -275951224 -100402889 -275951224 -275951224 -398078855 -398078855 -398078855 -388321940 -388321940 -388321940 -388321940 -275951224 -388321940 -275951224 -275951224 -100402889 -100402889 -100402889 -100402889 -81587938 -81587938 -81587938 -81587938 -81587938 -100402889 -100402889 -138853005 -138853005 -138853005 -100402889 -100402889 -81587938 -81587938 10371754 -81587938 10371754 10371754 10371754 10371754 10371754 10371754 10371754 10371754 43344227 10371754 10371754 10371754 10371754 -16451971 -14088920 -14088920 -14088920 -16451971 -14088920 -16451971 -16451971 -16451971 -16451971 -51048918 -51048918 -81587938 -51048918 -81587938 -81587938 -81587938 -51048918 -51048918 -16451971 -16451971…

Constraints:

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

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