HINT. To all whose solution using merge sort gets WA on test #5.

Solving the problem using the merge sort approach (counting inversions while merging subsequences - plus one inversion in a case of element from the left subseq greater than the element from the right) looks feasible (and maybe evident) to implement. But there is one caveat: it is crucial to count not only the one inversion in a case *cur_left > *cur_right, but count elements in a range [cur_left + 1, right_begin) as "inverted" too. That follows from the fact that merged subarrays are sorted in ascending order, so if we encountered the (*cur_left > *cur_right) case, then elements in a range [cur_left + 1, right_begin) satisfies that too and could be counted as inversions.

Hope I stated that clearly.

*Edited by author 04.05.2019 18:59*

*Edited by author 06.05.2019 06:44*