Skills101
← All coding problems

Count Inversions

mediumPlacement Coding+20 XPTime limit 2s

An inversion is a pair of positions i < j with a[i] > a[j] — two elements that are in the wrong order. Count the inversions. (It measures how far the array is from being sorted.)

Input:

  • line 1: n
  • line 2: n integers

Output: the number of inversions (up to about 5·10⁹ — use 64-bit integers).

Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ values ≤ 10⁹.

Think about it: modify merge sort. While merging two sorted halves, when an element from the right half is placed before the remaining elements of the left half, it forms an inversion with each of them — add that count all at once.

Sample input 1

5
2 4 1 3 5

Sample output 1

3

Sample input 2

3
1 2 3

Sample output 2

0

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.