TPGA - The Permutation Game Again

no tags 

Since YoMamaSoFat was able to answer Blackhood's and Kira's question as in (though with a little help from your side), it was my turn to ask him a question. This would again be a coding question as you might be knowing he is a noob in coding. I gave him a permutation of N distinct integers from 1...N and asked him the rank of the permutation when all possible permutations of the integers are arranged lexicographically. eg for N=3, all possible permutations arranged lexicographically would be:-

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

From the above, rank of 1 2 3 would be 1, rank of 1 3 2 would be 2 and so on...


NOTE:- You may assume it is the same permutation which Blackhood gave him in to tell the no. of inversions for each integer in it.Wink



First line of the input contains t, the no. of test cases. (1<=t<=10)

2*t lines follow, two for each test case.

Each test case begins with an integer N , the no of elements in the permutation.(1<=N<=200000)

The next line contains N space separated distinct integers from 1...N,  representing the permutation.


For each test case, print the rank of permutation %1000000007 on a new line.


3 2 1
2 1 4 3

hide comments
kshubham02: 2019-08-24 21:26:48

Time limit too strict.
Compulsory to do with BIT because of its marginal speed advantage over SegTree.

Last edit: 2019-08-24 21:38:40
eulerkochy: 2018-12-14 06:09:24

O(nlogn) works fine..little bit combi+ BIT !

akjol2049: 2018-12-05 06:26:53

NlogN TL.. does O(N) solution exist?

jmr99: 2018-07-19 17:51:39

getting wrong answer again and again !!

be1035016: 2018-06-25 22:24:12

BaZ Pro;)

vijayrit: 2017-07-05 22:08:03

Last edit: 2017-07-06 08:05:50
vijayrit: 2017-07-04 19:56:01

i am getting TLE ;-( Please help
Re: Brute force won't pass here. Have a better look at the constraints.

Last edit: 2017-07-04 20:34:08

Added by:null
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Motivated by