1352: New Sorting Algorithm

Time Limit: 1 Sec  

Memory Limit: 128 MB

Description

    We are trying to use a new sorting algorithm to sort a sequence with distinct integers.

    This algorithm will be end if the sequence is already in increasing order from left to right. Or for each step, suppose x is the leftmost integer, and y is the largest integer which is smaller than x in this sequence, we will move x to the right of y if y exists, otherwise we will move x to the right of the rightmost integer.

    So, how many steps will we use to sort a specific sequence with distinct integers by this new sorting algorithm?

    For example, we will use 7 steps to sort the sequence 7 1 5 2:

    7 1 5 2 --> 1 5 7 2 --> 5 7 2 1 --> 7 2 5 1 --> 2 5 7 1 --> 5 7 1 2 --> 7 1 2 5 --> 1 2 5 7

Input

    The first line has an integer T, means there are T test cases.

    For each test case, there is one integer N (2 <= N <= 105) in the first line, means the sequence has N distinct integers. Then there are N integers in the next line describing this sequence. Every integer of this sequence is in range [0, 109].

    The size of the input file will not exceed 5MB.

Output

    For each test case, print an integer in one line, indicates the number of steps we will use to sort this sequence by the new soring algorithm.

Sample Input

333 7 847 1 5 255 4 3 2 1

Sample Output

0710

HINT

 

Source

 

   对于节点X 。f(x)=i+1 。 {X-1 ,X -2 ,...X-i}均在X左端出现。

 1、1的右边没有升序排列好  。   

Ans=  f(1) + f(2) +.....f(N) ;

 2 、1的右边升序排列好

 Ans=  f(num[1]) + f(num[2]) +.....f(num[1所在位置-1]) ;

#include 
      
       #include 
       
        #include 
        
         #include