文理学院程序设计在线练习


Inversion

Time Limit: 1 Second(s)    Memory Limit: 128 MB

Total Submission(s): 1   Accepted Submission(s): 1
Problem Description

Give a sequence A with N distinct integers(1<=Ai<=N). For each pair of inversions in the sequence, you need to select one of the elements.now we need you to make the number of element you select is minimum.

Input

The first line contains an integer T, represents the number of testcases.
For each testcase, the first line contains an integer N;
the second line contains N integers, represents A1,A2,….,AN; (T<=10,1<=N<=100000,1<=Ai<=N).

Output

For each testcase, output one line contains an integer represents the minimum number of element you can select.

Sample Input
1
5
5 4 3 2 1
Sample Output
4
Hint

For an array contains N non-negative integers, A[1.. N], for each pair of numbers which satisfy i < j and A[i] > A[j], we call (A [i], A [j]) is a pair of inversion in the array A.

Source

2017绍兴市技能竞赛