CF2222C.Median Partition

You are given an array $ a $ with an odd length $ n $ consisting of positive integers. You are required to partition the sequence into several subarrays $ ^{\text{∗}} $ with odd lengths and the same median $ ^{\text{†}} $ . Your task is to find the maximum number of subarrays.

More formally, you are required to find a strictly-increasing sequence $ k $ with a length of $ (p+1) $ where $ k_1=1 $ and $ k_{p+1}=n+1 $ , such that for every $ 1\le i\le p $ , the medians of the sequences $ [a_{k_i},a_{k_i+1},\ldots,a_{k_{i+1}-1}] $ are all the same. The parity of $ k_i $ and $ k_{i+1} $ should be different. Your task is to find the biggest possible value of $ p $ .

$ ^{\text{∗}} $ An array $ b $ is a subarray of an array $ a $ if $ b $ can be obtained from $ a $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

$ ^{\text{†}} $ The median of an array with an odd length $ x $ is the $ \lceil\frac{x}{2}\rceil $ -th element of the array after it is sorted in non-decreasing order.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 1000 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1\le n \lt 5000 $ , $ n $ is odd) — the length of $ a $ .

The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1\le a_i\le 10^9 $ ) — the elements of $ a $ .

It is guaranteed that the sum of $ n^2 $ over all test cases does not exceed $ 5000^2 $ .

For each test case, output a single integer — the maximum number of subarrays.

In the first test case, it is optimal to partition $ a $ into $ [\underline 3, \underline 3, \underline{2, 4, 3}] $ .

In the second test case, it is optimal to partition $ a $ into $ [\underline{9, 5, 7}, \underline 7, \underline{4, 7, 7}] $ .

In the third test case, since all the elements are the same, you can partition each element into a separate subarray.