# Yet Another Sorting Algorithm

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

**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