Little Elephant and Median

All submissions for this problem are available.
Little Elephant from Zoo of Lviv likes medians so much. Let us define median term for some array A. Let B be the same array A, but sorted in nondecreasing order. Median of A is B_{m} (1based indexing), where m equals to (n div 2)+1. Here 'div' is an integer division operation. So, for a sorted array with 5 elements, median is the 3rd element and for a sorted array with 6 elements, it is the 4th element.
Little Elephant has an array A with n integers. In one turn he can apply the following operation to any consecutive subarray A[l..r]: assign to all A_{i} (l <= i <= r) median of subarray A[l..r].
Let max be the maximum integer of A. Little Elephant wants to know the minimum number of operations needed to change A to an array of n integers each with value max.
For example, let A = [1, 2, 3]. Little Elephant wants to change it to [3, 3, 3]. He can do this in two operations, first for subarray A[2..3] (after that A equals to [1, 3, 3]), then operation to A[1..3].
Input
First line of the input contains single integer T  the number of test cases. Then T test cases follow, each of such format: first line  integer n, second line  array A consisted of n integers.
Output
In T lines print the results for each test case, one per line.
Constraints
1 <= T <= 100
1 <= n <= 30
1 <= A[i] <= 10^9
Example
Input: 2 3 1 2 3 4 2 1 1 2 Output: 2 1
Author:  witua 
Tester:  subra 
Editorial  http://discuss.codechef.com/problems/MEDIAN 
Tags  may12, medium, witua 
Date Added:  5122011 
Time Limit:  0.339965 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 