CT59420

Dorian Counts the vials

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the lotus ponds of Tranquil Basin close for winter, Dorian must finish the vials 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 <= 3446; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1272 69241370 478852864 293654315 90552022 894983724 820986754 179424143 702715328 753721873 760322265 477622610 837198346 882699991 363153183 725199582 79146543 853713759 315383798 632567518 397563071 132552783 501511184 20938200 356272784 436331040 287144644 81618833 717458683 878953166 803710202 361754336 6548066 541270696 266955803 200711707 985211808 642691956 474331906 319283046 248354876 504285336 197007829 749886774 763705147 931229670 201399342 578833877 283264797 87543232 691676501 642068045 412174540 203733432 623086172 43387881 657678948 331969376 24654472 484285652 211860425 590343618 79840438 210158486 817848397 301501343 662636646 104659327 728521871 283224871 491755389 945169414 219808968 734593229 916323545 763419455 299948248 203350343 718076538 615049588 410687734 290873…
Output: 408865

Example 2:

Input: 956 947605321 954126971 408238025 403593454 856260283 990277376 586794002 914582637 103957723 824745728 550517375 184556254 924864187 114886445 832485062 930437625 416842038 128853413 487254320 84986274 598410527 827736910 848340416 667093035 923477543 712120698 344143376 411230651 594311781 993875916 361156883 837263864 997920976 378051934 247994797 96175853 769528088 162418882 774325854 146724715 186165341 839713494 721760416 991211770 804496199 329470386 134231405 406502361 26913946 415317175 804967822 858274985 751441826 508383900 991176248 946830241 978274183 73731684 42562560 279362601 512608863 240256382 228182093 956032558 390634986 464720886 425126655 630839059 854725501 109532954 10045827 514870369 579540697 636904994 42275905 336668461 756055935 494050469 357767648 218355631 688…
Output: 225895

Example 3:

Input: 224 880207326 881068595 272196996 323068570 938755573 704859775 985580155 170098831 267038205 558133840 788738313 241616310 885327911 376174041 518021986 200345543 252122408 189419622 652506705 907431360 505939885 73223241 831851145 702452523 887080325 647426690 782551639 157504544 896765269 681547321 321593586 296111115 496554701 381242488 238112166 546411927 688860792 1256986 989278522 311065833 474363325 1866679 835966586 65949962 809506115 632761019 762363365 483940836 268813426 702794703 620068288 936117439 325175260 820938277 70633922 530068902 858974778 335885161 430855500 593313041 683540581 592711889 958269360 53564331 586131194 889889581 476943611 765577861 107661209 330816825 396010436 707108839 255848374 55610421 68925167 255694837 259061136 963442178 695128664 762251720 393993…
Output: 12937

Constraints:

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

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