{"id":"c71aa6a5-2e2b-488a-b7dc-f0c33bbb20df","name":"Count Inversions","description":"1. Given an array of integers. Find the Inversion Count in the array. \r\n2. For an array, inversion count indicates how far (or close) the array is from being sorted. If array is already sorted then the inversion count is 0. If an array is sorted in the reverse order then the inversion count is the maximum. \r\n3. Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.\r\n","inputFormat":"A number n, denoting number of elements\r\nn number of integers, denoting elements of array\r\n","outputFormat":"Print the count of total inversions\r\n","constraints":"1 &lt;= N &lt;= 10^5\r\n1 &lt;= arr[i] &lt;= 10^6\r\n","sampleCode":{"cpp":{"code":"#include <iostream>\n#include<vector>\n\nusing namespace std;\n\nint main() {\n // write ypur code here\n}"},"java":{"code":"import java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[]args) {\r\n //write your code here\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"5\r\n2 4 1 3 5","sampleOutput":"3","questionVideo":"https://www.youtube.com/embed/uojx--MK_n0","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"cb36811c-9cd7-4d80-aa52-ae9b8409862a","name":"Searching And Sorting For Intermediate","slug":"searching-and-sorting-for-intermediate-10001","type":0},{"id":"47592075-d9b0-4d38-a20e-211df31424a7","name":"Count Inversions","slug":"count-inversions","type":1}],"next":{"id":"819c30be-4818-4c57-bf02-0c821c9a4733","name":"Count Inversions MCQ","type":0,"slug":"count-inversions-mcq"},"prev":{"id":"d0ee512b-9b8f-4faf-b783-c36eca2087cf","name":"Find Minimum In Rotated Sorted Array MCQ","type":0,"slug":"find-minimum-in-rotated-sorted-array-mcq"}}}

Count Inversions

1. Given an array of integers. Find the Inversion Count in the array. 2. For an array, inversion count indicates how far (or close) the array is from being sorted. If array is already sorted then the inversion count is 0. If an array is sorted in the reverse order then the inversion count is the maximum. 3. Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

{"id":"c71aa6a5-2e2b-488a-b7dc-f0c33bbb20df","name":"Count Inversions","description":"1. Given an array of integers. Find the Inversion Count in the array. \r\n2. For an array, inversion count indicates how far (or close) the array is from being sorted. If array is already sorted then the inversion count is 0. If an array is sorted in the reverse order then the inversion count is the maximum. \r\n3. Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.\r\n","inputFormat":"A number n, denoting number of elements\r\nn number of integers, denoting elements of array\r\n","outputFormat":"Print the count of total inversions\r\n","constraints":"1 &lt;= N &lt;= 10^5\r\n1 &lt;= arr[i] &lt;= 10^6\r\n","sampleCode":{"cpp":{"code":"#include <iostream>\n#include<vector>\n\nusing namespace std;\n\nint main() {\n // write ypur code here\n}"},"java":{"code":"import java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[]args) {\r\n //write your code here\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"5\r\n2 4 1 3 5","sampleOutput":"3","questionVideo":"https://www.youtube.com/embed/uojx--MK_n0","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"cb36811c-9cd7-4d80-aa52-ae9b8409862a","name":"Searching And Sorting For Intermediate","slug":"searching-and-sorting-for-intermediate-10001","type":0},{"id":"47592075-d9b0-4d38-a20e-211df31424a7","name":"Count Inversions","slug":"count-inversions","type":1}],"next":{"id":"819c30be-4818-4c57-bf02-0c821c9a4733","name":"Count Inversions MCQ","type":0,"slug":"count-inversions-mcq"},"prev":{"id":"d0ee512b-9b8f-4faf-b783-c36eca2087cf","name":"Find Minimum In Rotated Sorted Array MCQ","type":0,"slug":"find-minimum-in-rotated-sorted-array-mcq"}}}
plane

Editor

Loading...

Count Inversions

hard

1. Given an array of integers. Find the Inversion Count in the array. 2. For an array, inversion count indicates how far (or close) the array is from being sorted. If array is already sorted then the inversion count is 0. If an array is sorted in the reverse order then the inversion count is the maximum. 3. Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

Constraints

1 <= N <= 10^5 1 <= arr[i] <= 10^6

Format

Input

A number n, denoting number of elements n number of integers, denoting elements of array

Output

Print the count of total inversions

Example

Sample Input

5 2 4 1 3 5

Sample Output

3

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode