GONESORT  GOne Sort
After Killing RaOne GOne had nothing to do. HE started reading books and became a avid book reader.
To avoid purchasing books and he started working in a library.
Every evening he had to arrange the books in the shelf in increasing order of their serial number.
Every book in a the library is is numbered .
..
GOne found a 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 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 wil contain b numbers. each bi denoting the serial number of the book.
Output
For each test case ouput single number 'res'  denoting the minimum 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, 10^7], number of test cases <=100.
hide comments
vetox:
20170101 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.


flyingduchman_:
20161205 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.


bluefa:
20160318 02:32:05
there is solution with O(nlogn). 

ABHISHEK004:
20151209 20:29:08
@Devil D test file of the problem should be updated as test cases are very weak


Abhilash:
20150825 14:21:57
0.00 with n^2 

i_am_looser:
20150617 07:05:06
ans for 10 22 9 33 21 50 41 60 80 is 6.


jinkies:
20141020 14:45:25
pretty simple, use simple n^2 algo... though idk why using lcs was giving WA 

rajul:
20140408 12:52:04
very weak test cases.. just code and submit _ no need to think too much 

AlcatraZ:
20140327 11:35:39
Good Question.. Must do 

:
20130719 06:17:13
good question time limit is enough O(n^2)

Added by:  Devil D 
Date:  20120405 
Time limit:  0.100s0.190s 
Source limit:  20000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own 