TPGA - The Permutation Game Again

no tags 

Since YoMamaSoFat was able to answer Blackhood's and Kira's question as in 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. For example, 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 TPGAME to tell the number of inversions for each integer in it.Wink

Input

First line of the input contains t, the number of test cases (1 <= t <= 10). 2 * t lines follow, two for each test case. Each test case begins with an integer N, the number 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
depressedboy: 2022-01-20 14:47:42

USE BIT
avoid extra ds like ordered_set

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