spoj#TPGA. The Permutation Game Again
The Permutation Game Again
Since YoMamaSoFat was able to answer Blackhood's and Kira's question as in http://www.spoj.com/problems/TPGAME/ (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...
HELP HIM!
NOTE:- You may assume it is the same permutation which Blackhood gave him in http://www.spoj.com/problems/TPGAME/ to tell the no. of inversions for each integer in it.
Input
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.
Output
For each test case, print the rank of permutation %1000000007 on a new line.
Example
Input:
3
1
1
3
3 2 1
4
2 1 4 3
Output: 1
6
8