CT35765

Ranger's Ledger of crates

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the alabaster quarry of Whitestone close for winter, Ranger must finish the crates ledger - one figure at a time. Task: Print the number of inversions: index pairs (i,j) with i<j but a[i] > a[j]. Input format: First line: n. Second line: n integers. Output format: Print the inversion count (fits 64-bit). Constraints: 1 <= n <= 1641; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 1104 -245188 -219508 954772 -271330 961445 369001 824838 -285620 155715 600508 -393899 174586 499549 -804699 -9615 848006 881735 375214 250719 674740 -258766 666912 862877 939955 -265180 -832041 -83957 626392 840119 -1874 725408 -977209 -807218 -68749 572028 119681 446836 -970998 -739567 625721 -373324 -754933 -439482 123047 20726 54793 579400 -334712 -556833 939172 -463784 285232 -30939 804123 719136 -281591 114073 -325916 -384322 756819 109943 427909 -677787 -270509 -644281 443895 54659 -561074 -944517 -300521 695034 918196 -804412 436608 249998 -563129 532414 -88713 -484309 -844214 803531 -144244 541510 230173 -978538 -519449 -770695 -284814 -376058 505422 -261306 846284 158451 -242376 514375 -319338 -685680 521267 -432156 886144 -254279 509320 120205 -735843 -449156 176829 834060 66808…
Output: 312082

Example 2:

Input: 334 -712792 -182149 897686 -578629 -240411 -311637 166195 -286224 -21777 935947 705469 649802 348071 -73739 376415 238046 607795 -230424 253528 43176 -301181 -642303 -288944 455822 -378445 -999776 -813515 526913 -792320 681455 633174 -502004 -823346 776897 -110995 694595 -659792 7259 -16536 349482 -968205 -730946 860467 588967 168205 -155647 938458 -518398 56217 753183 82266 360172 764368 315510 -869696 -349746 929669 513364 660588 -22756 291728 703132 -95906 -881930 -292401 -329611 266728 -105761 17544 753965 -538474 450059 291904 195474 143290 978177 -762393 977749 -813571 117522 490552 -595411 -933813 448269 168662 -459816 816250 21998 -793200 -773876 -713257 -856234 -643874 -455873 -56062 -169943 974770 -102193 -56501 820816 721183 749824 231933 -837183 124925 56758 -239304 -911085 149…
Output: 28984

Example 3:

Input: 667 24021 950484 408063 376645 995244 -637500 -715990 -341290 522282 -879387 -204333 -711546 192947 -539495 93295 -589583 910906 102560 -742037 -116837 396516 409005 -328181 -971653 -941094 812593 845828 708936 -142135 567144 -186286 -122959 -972779 -609847 555245 -137900 -651319 -579945 504228 -257440 -886803 147217 691024 -536718 941160 983998 418018 220708 -427429 -168363 -118573 -226418 312447 -759696 224420 551681 295474 79280 -613661 224419 574578 825762 66039 -228342 795761 69630 -842372 -853522 -15155 665029 748024 622162 621442 -897692 -881672 385037 204544 612011 350580 -361870 221922 539873 -412052 632568 887624 -75358 -16529 627778 -302087 430362 138052 -743647 229510 674288 -962084 130884 -406290 -489978 92817 878587 298372 589883 -472552 791852 719658 -56680 511525 -306220 72…
Output: 111812

Constraints:

1 <= n <= 1641; -1000000 <= a[i],x <= 1000000.

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