CT60006

Last shelves of Brevin

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Brevin inherited the print shop at the island market of Coralcove along with its curious bookkeeping system for shelves. Time to make sense of it. 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 <= 1486; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1417 820661273 485824297 64351645 577533289 159306606 783139904 408074810 822820210 732119018 86652773 509930499 435755846 700409299 591777552 498211330 761537831 295845429 703982932 75587887 131089180 14680890 21507995 426778260 394236228 819580854 683302040 460666071 250304754 385172644 201325626 243402048 355977369 255942111 971275044 206418265 436813441 583770405 225918908 23739874 137605252 226526117 875536882 319794226 94925826 603012217 78644390 540115518 638065807 298155836 102746152 221076445 583738585 748923874 534022314 148735727 660033542 993044182 72183910 32016284 337351370 887888745 298463388 970497057 912585197 693775040 507531736 361760454 805419717 556282223 239015013 731994567 323931191 660755388 233026609 396120779 831157979 491440480 95352032 199580418 736035446 367596…
Output: 505228

Example 2:

Input: 122 652840094 408559519 348600857 415909087 953039485 131337315 167441096 59196204 406921819 355965642 759976373 389694141 962686047 598527701 79981096 335904263 777568006 947050307 912004218 50766391 350985611 494548099 820487023 548307328 558051897 434773017 617686116 344938319 499730689 947455266 86032149 251743669 117793182 789328284 236547219 579935341 64476495 125605495 492365908 342430667 34178874 571528613 221577934 205660201 489988080 579023987 250252469 417791612 262108568 785157813 737304503 278099006 830066396 465401213 625255356 618216539 111721690 330922998 623888245 367862126 148481961 732382842 294891185 356956647 158231979 943359087 801071604 813380963 861636153 67270655 486594649 304125211 166076095 834446300 518949759 224555261 424963042 727925133 642504414 759363154 344…
Output: 3203

Example 3:

Input: 1066 681 443 755 383 487 677 196 559 690 328 59 186 816 162 142 595 419 763 738 666 642 208 741 679 777 18 539 695 180 772 53 823 797 709 765 947 271 952 560 150 1028 689 867 524 78 255 1049 623 249 498 174 1056 222 903 871 476 771 80 494 1042 366 232 372 576 130 736 548 1 287 852 455 254 484 481 580 982 835 184 304 219 794 640 890 29 965 544 220 252 985 340 338 996 412 600 551 604 1061 473 546 596 54 701 929 863 35 392 403 882 369 813 902 423 786 648 537 725 156 148 805 639 718 586 131 145 570 1004 858 543 541 916 333 22 359 457 619 534 740 418 885 517 655 480 577 756 442 808 431 305 569 356 746 748 10 371 4 620 456 692 485 549 1001 1046 176 41 264 904 189 634 869 1006 312 492 995 225 617 1050 886 122 728 504 224 470 635 467 175 669 528 388 408 237 349 106 607 495 742 446 398 900 829 259 …
Output: 290149

Constraints:

1 <= n <= 1486; 0 <= a[i],x <= 1000000000.

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