All Submissions


A DEQUE as you all know is a data structure which allows constant time insertion and removal from both ends. Now we are gonna use the same to sort an array of integers data[]. For each element x in data we can do following operations only:
1. Push x onto the front of an existing deque.
2. Push x onto the back of an existing deque.
3. Create a new deque with x being the only member.

The elements in data must be processed in the same order as is given. We can not skip any element of data temporarily and process it some time later. We are also not allowed to insert an element in the middle of an existing deque, as specified only front and back insertions are allowed. To keep things simple we will not have any duplicate entries in data.

Once all the elements in the array data are processed wisely, we should be able to place the created deques on the top of one another in any order of our choice so that all the deques together form a sorted sequence. Now, you are gonna find what will be the minimum number of deques required to sort the given array.

Input:

The very first line will contain single integer T representing the number of test cases. T test cases then follow.

The first line of each test case will be N the size of array data[]. The next line contains N integers.

Please use scanf to take input.

Output:

One line for each test case which is an integer telling the minimum number of deques required.

Limits:

1<=T<=200
0-10000<=data[i]<=10000; data[i] being the ith element of data.

Sample Input

3
10
50 45 55 60 65 40 70 35 30 75
6
3 6 0 9 5 4
10
0 2 1 4 3 6 5 8 7 9

Sample Output

1
2
5

Clarification for third test case:
The deques are {0,1}, {2,3}, {4,5}, {6,7}, and {8,9}. Please note that you have to stack the deques on one another in any arbitrary possible order so that the final sequence is sorted.

Problem Setter: Dhruva Bhaswar
Problem Tester: Arjun Singh Bhatia


Languages: Brain,C,C++,Java,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0