Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem C: 二队-上海-逆序对

Problem C: 二队-上海-逆序对

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 36  Solved: 14
[Submit][Status][Web Board]

Description

有一个长度为N的数列A,A中的元素各不相同且均在[1,n]的范围内。对于数列中的每一对逆序对,你需要选出其中的某一个元素,使得最后选中的数的集合大小最小。

Input

第一行一个正整数T(T<=10),表示共有T组数据。
对于每组数据,第一行一个正整数N(1<=N<=100000)。
接下来一行,每行N个数,表示数列A中的N个数(1<=Ai<=100000)。

Output

对每组数据输出一行,即最小的集合大小。

Sample Input

1
5
5 4 3 2 1

Sample Output

4

HINT

[Submit][Status][Web Board]