oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

inversions Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

inversions.html

An inversion in a sequence A[1..n] is defined as i, j, 1 ≤ i < j ≤ n, such that A[i] > A[j]. For example, the sequence A = {1, 5, 2, 4, 3} contains 4 inversions, from the pairs (5, 2), (5, 4), (5, 3), (4, 3).

Your task is simple: Given a sequence, determine the number of inversions in the sequence.

Input

The first line of input will be an integer T (T ≤ 100), stating the number of test cases.

T test cases follow, each in the following format:

First line: An integer N (N ≤ 50,000),

Next line: N integers, giving the values of A[1], A[2], ..., A[N]. You may assume that 0 ≤ A[k] ≤ 2,147,483,647 for all k ≤ N.

Output

For each test case, output a single number: The number of inversions in the sequence.

Sample Input 1

3
5
1 5 2 4 3
5
1 2 3 4 5
6
6 5 4 3 2 1

Sample Output 1

4
0
15

Tags

Data Structure, Divide and Conquer

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110021s32MBMinimum
2011s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o inversions -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.