CT59670

The Middle So Far at Brineport

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Petr found an old ledger of ledgers in the signal tower attic at the smokehouses of Brineport. The margin notes pose a precise question. 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: 3383 -367517978 934259423 753989137 942011805 -825246732 360316158 864052377 -418247522 151952605 -485526222 697025410 885812516 -30820691 -623673085 -184307551 -110811695 375908818 -695656221 362636675 -136595873 -763442110 882162706 866994364 -2968721 -582597188 -33557354 -7871080 -435966412 -121113587 600030070 -179511752 521136972 -201474213 547754602 -714600873 -22958251 -755119218 769596518 -487223939 591957822 -796821715 -551488049 864159507 268228494 -5792951 956874018 811420115 -686526169 -761472720 -258809345 -503730312 83048019 -491488674 709275534 489925265 -83151912 855204931 368775753 784175400 -140657876 -531809136 819874254 778781168 -893415623 794584640 -952518063 -173777764 115108519 638670098 -184477579 -484955183 25917355 901858247 -363820375 644807055 -363277164 -58948…
Output: -367517978 -367517978 753989137 753989137 753989137 360316158 753989137 360316158 360316158 151952605 360316158 360316158 360316158 151952605 151952605 -30820691 151952605 -30820691 151952605 -30820691 -30820691 -30820691 151952605 -2968721 -2968721 -30820691 -7871080 -30820691 -30820691 -30820691 -30820691 -30820691 -30820691 -30820691 -30820691 -30820691 -30820691 -30820691 -30820691 -30820691 -30820691 -33557354 -30820691 -30820691 -22958251 -22958251 -7871080 -22958251 -22958251 -30820691 -30820691 -30820691 -30820691 -30820691 -22958251 -30820691 -22958251 -22958251 -7871080 -22958251 -22958251 -22958251 -7871080 -22958251 -7871080 -22958251 -22958251 -22958251 -7871080 -22958251 -22958251 -22958251 -7871080 -22958251 -7871080 -22958251 -22958251 -22958251 -22958251 -30820691 -2295825…

Example 2:

Input: 2936 915823042 -979213002 -636774881 791238769 470426497 669100265 -368377315 493753143 743636936 -757377672 972468795 898203110 -405511539 -520926664 853280841 447466017 620398008 -103370122 -660100105 -179071937 219272891 -124962073 -3125496 -642453030 -929443222 -233424945 620430945 210496932 679584882 -707060593 905842032 -251765441 -320622551 -902728814 -255873132 879457641 746761731 45944577 614570428 -22201464 108685229 -273660701 -544263461 -213040984 489740473 621951947 953515612 712643903 517484760 434275221 -637483712 -636748085 794475307 -264888652 -331271262 -498274609 993493969 489917699 335584877 371386357 -542983322 652762558 -481765576 -676332033 -153969607 -565362784 799752927 398735332 -892639527 -711132345 618919156 -79059158 678543756 199362840 604118829 630248601 5813…
Output: 915823042 -979213002 -636774881 -636774881 470426497 470426497 470426497 470426497 493753143 470426497 493753143 493753143 493753143 470426497 493753143 470426497 493753143 470426497 470426497 447466017 447466017 219272891 219272891 -3125496 -3125496 -103370122 -3125496 -3125496 210496932 -3125496 210496932 -3125496 -3125496 -103370122 -103370122 -103370122 -3125496 -3125496 45944577 -3125496 45944577 -3125496 -3125496 -22201464 -3125496 -3125496 45944577 45944577 108685229 108685229 108685229 45944577 108685229 45944577 45944577 -3125496 45944577 45944577 108685229 108685229 108685229 108685229 108685229 45944577 45944577 -3125496 45944577 45944577 45944577 -3125496 45944577 -3125496 45944577 45944577 108685229 108685229 199362840 108685229 199362840 108685229 108685229 108685229 19936284…

Example 3:

Input: 525 -251863825 -543232014 -918137183 57266006 -164304508 972561191 302585916 719728980 81575725 -703921913 49162592 -635779235 384922874 521746477 635449667 -465437184 854206848 291907181 -200183164 932844472 -930518250 337403880 -913910769 969631866 -811936776 -331078877 360893845 -509333625 720065658 -629891611 14160820 -203245382 716190787 -746368809 -872119943 790018354 523396204 115954797 -898222825 -349561056 -479571716 -214679160 294743923 149764339 240801688 195337500 699077815 -598712184 -455205537 984019049 547892624 -173251715 -79270173 426611535 538951217 584640596 -904333466 895756630 -555929151 789554981 -201732869 -148584266 -809125761 -775495572 -104788994 213881941 -879127493 664058323 73376650 842177907 -432789226 -122477524 -967191182 76427280 750740996 723012425 -679249…
Output: -251863825 -543232014 -543232014 -543232014 -251863825 -251863825 -164304508 -164304508 57266006 -164304508 49162592 -164304508 49162592 49162592 57266006 49162592 57266006 57266006 57266006 57266006 57266006 57266006 57266006 57266006 57266006 49162592 57266006 49162592 57266006 49162592 49162592 14160820 49162592 14160820 14160820 14160820 49162592 49162592 49162592 14160820 14160820 -164304508 14160820 14160820 49162592 49162592 57266006 49162592 49162592 49162592 57266006 49162592 49162592 49162592 57266006 57266006 57266006 57266006 57266006 57266006 57266006 49162592 49162592 14160820 14160820 14160820 14160820 14160820 49162592 49162592 49162592 14160820 14160820 14160820 49162592 49162592 49162592 49162592 57266006 57266006 57266006 57266006 57266006 57266006 73376650 73376650 7337…

Constraints:

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

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