# Reverse Pairs

Hard
0/120
Average time to solve is 50m
Contributed by

## Problem statement

You are given an array/list say ‘ARR’ of size ‘N’. We call pair (i, j) a Reverse Pair when i < j and 'ARR[i]' > 2 * 'ARR[j]'.

Your task is to find the number of Reverse Pairs present in given 'ARR'.

For example :

``````For the array [50, 21, 9], if we follow 1-based indexing, the Reverse Pairs are (1, 2), (1, 3) and (2, 3). Thus, the total count i.e. the answer becomes 3.
``````

Note :

``````A single index of the pair (i, j) can be used multiple times.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 <= T <= 5
2 <= N <= 3000
1 <= ARR[i] <= 10^5

Where 'ARR[i]' denotes the i-th elements in the array/list.

Time Limit: 1 sec
``````
##### Sample Input 1 :
``````1
6
1 2 3 2 3 1
``````
##### Sample Output 1 :
``````2
``````
##### Explanation Of Sample Input 1 :
``````Test case 1:
Given that we follow 1-based indexing, for the array {1, 2, 3, 2, 1}, the pairs satisfying the conditions of Reverse Pairs are
For i = 3, arr[i] = 3 and for j = 6, arr[j] = 1.
For i = 5, arr[i] = 3 and for j = 6, arr[j] = 1.
Hence there are two possible pairs.
``````
##### Sample Input 2 :
``````2
6
6 4 8 2 1 3
5
2 4 3 5 1
``````
##### Sample Output 2 :
``````6
3
``````
##### Explanation Of Sample Input 2 :
``````Test case 1:
Given that we follow 1-based indexing,The possible pairs satisfying the conditions of Reverse Pairs are (1, 4), (1, 5), (2, 5), (3, 4), (3, 5), (3, 6). Thus, the answer is 6.

Test case 2:
Given that we follow 1-based indexing, The possible pair of indices satisfying the above condition are (2, 5), (3, 5), (4, 5). Thus, the answer is 3.
``````
Console