CT59816

The Disorder Count of the Sunlit registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the floating docks of Skyharbor, Gautam studies rows of registers entries. One clean number will settle the guild's oldest argument. 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 <= 1054; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 271 93894970 943104472 474961990 51353249 53517596 64225426 637502834 328789112 45740093 560202684 315979406 267777341 628448099 305744909 293009941 647793274 647027800 352597560 390987404 596037941 580263059 400439275 90339947 176347473 414328898 78236273 79560276 439161055 826030250 770870152 756765466 659602876 63568412 341852007 799375931 45691511 635494890 365894201 646047496 631832499 421222132 519606590 604791991 217012061 22024961 188470568 697849156 229670300 905624635 581218477 808620899 855005911 163194307 609599865 930433578 739247949 477177127 447322404 556955491 24450762 960908020 754447816 341529069 70584568 69004081 169201773 207193531 502270546 373992165 70535652 626566808 667215074 47203509 996967220 986630637 593217237 995154060 760392428 993507297 931794941 970131024 47…
Output: 17334

Example 2:

Input: 499 99768212 604786140 807227019 678430754 694004381 369364023 230603660 271081508 650258022 236348691 851535483 21654741 714683699 409784733 795311220 718077797 997207066 208219130 558559292 689927611 823374445 68425303 606991045 106688659 727799629 868615683 808300023 595287742 508795411 509605191 246558232 787334808 66165869 117353374 658707448 516128857 847409213 802608445 989270921 278099191 644646649 39553981 741656379 286625312 909937637 984085707 244056950 303377255 859188217 208101757 235918611 560482152 204021218 302236842 884496719 663255566 721267025 451443865 550007733 641473499 691954881 44246736 561919351 517394809 386655739 922349315 955022679 612944852 788963830 462724153 665044676 50447916 637833259 373591831 624351480 192188691 4070746 283875709 579541365 73387249 250936…
Output: 62968

Example 3:

Input: 79 298294137 409193016 723140240 71206420 23570498 562874181 57113574 507291055 366238942 633600385 987492525 283093127 339246241 135148462 376936379 429281487 298154086 44993236 256933363 679914084 737087803 508232829 10228221 64900356 239029608 694305874 974685069 461234482 653464524 525374368 11490243 775718887 408345491 127382671 263237038 783257158 839913234 623442805 396304811 754694154 113482964 604724677 440845730 309042354 291934203 518353822 74016538 472004835 494676163 895938741 396687134 853659241 872477178 762388071 312137815 596741678 454241466 15772960 756147530 642010071 35405454 65985082 121963393 469990675 451221410 295805516 296675564 325301631 896826308 177381953 166235132 921352573 779886983 540819335 232238724 571362029 330763272 746665371 651711657
Output: 1403

Constraints:

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

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