TPGA - The Permutation Game Again

no tags 

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.Wink

 

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

hide comments
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:BaZ
Date:2017-07-03
Time limit:0s-0.159s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Motivated by www.spoj.com/problems/PERMRANK