GONESORT - G-One Sort

After Killing RaOne G-One had nothing to do, so he started reading books and became an avid book reader.

To avoid purchasing books he started working in a library.

Every evening he had to arrange the books on the shelf in increasing order of their serial number.

Every book in the library is numbered.

..

G-One found an ingenious way of arranging the books.  He can remove any book from the shelf and put it either at the beginning or at the end of the shelf.

For example if the books are arranged in the order below:

    2  3  1  7  4  5  6

he can make it sorted by removing '1' and placing it at the beginning and then removing '7' and placing it in the end.

Since the book shelf can be very big and can have a large number of books, he needs your help to tell him the minimum remove and place operations he needs to do.

Can you help him?

Input

1st line of the input contains number 't' denoting the number of shelves in the library. 2*t lines follow this

1st line of each test case will have single number 'b' - denoting number of books on the shelf.

2nd line will contain b numbers, each bi denoting the serial number of the book.

Output

For each test case output a single integer denoting the minimum number of remove and place operations needed to arrange the shelf.

Example

Input:
3
7
2 3 1 7 4 5 6
5
1 2 3 4 5
6
6 5 4 3 2 1

Output:
2
0
5

NOTE All the values will be in the range [0, 107], number of test cases ≤ 100.


Added by:Devil D
Date:2012-04-05
Time limit:0.100s-1s
Source limit:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own

hide comments
2017-01-01 19:38:37
Unnecessary white spaces and line breaks in the input file. Be wary of using BufferedReader in Java. Using Scanner is better. cin & scanf should pose no problem.

Cost me many NZEC errors in Java.
2016-12-05 18:55:40
One thing that is not mentioned in the question explicitly: Let's assume a list 10,20,30,40. You must assume there are 40 books in serial 1 2 3 ......40. You are given only 10,20,30,40 to determine how many of them will be moved.
Logic: longest perfect increasing sequence i.e. i,i+1,i+2 ... are never moved. so, n-LPIS length is the solution. Do spoj LPIS first to get it.
so, for 10,20,30,40 , LPIS length = 1(any of them). so 4-1 = 3 is ans.
2016-03-18 02:32:05
there is solution with O(nlogn).
2015-12-09 20:29:08 ABHISHEK004
@Devil D test file of the problem should be updated as test cases are very weak
for n=6
5 3 6 1 4 2
it accepts code with solution as 3 and 4
but actual output should be 4

Last edit: 2015-12-09 20:29:35
2015-08-25 14:21:57 Abhilash
0.00 with n^2
2015-06-17 07:05:06 i_am_looser
ans for 10 22 9 33 21 50 41 60 80 is 6.
sequentially put 41 33 22 21 10 9 on the top and it's done.
2014-10-20 14:45:25 jinkies
pretty simple, use simple n^2 algo... though idk why using lcs was giving WA
2014-04-08 12:52:04 rajul
very weak test cases.. just code and submit -_- no need to think too much
2014-03-27 11:35:39 AlcatraZ
Good Question.. Must do
2013-04-17 08:12:12 Arika Saputro
i think you must add that all case in this prob is consecutive..
ex
2 3 1 7 4 5 6 can be 1 2 3 4 5 6 7
but 2 1 7 5 6 can't be case because there are no 3 and 4.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.