Вам дан массив $$$a$$$ нечётной длины $$$n$$$, состоящий из целых положительных чисел. Требуется разбить последовательность на несколько подмассивов$$$^{\text{∗}}$$$ нечётной длины с одной и той же медианой$$$^{\text{†}}$$$. Необходимо найти максимальное количество таких подмассивов.
Формально, требуется найти строго возрастающую последовательность $$$k$$$ длины $$$(p+1)$$$, где $$$k_1=1$$$ и $$$k_{p+1}=n+1$$$, такую, что для каждого $$$1\le i\le p$$$ медианы последовательностей $$$[a_{k_i},a_{k_i+1},\ldots,a_{k_{i+1}-1}]$$$ совпадают. Паритет $$$k_i$$$ и $$$k_{i+1}$$$ должен быть разным. Ваша задача — найти максимально возможное значение $$$p$$$.
$$$^{\text{∗}}$$$Массив $$$b$$$ является подмассивом массива $$$a$$$, если $$$b$$$ может быть получен из $$$a$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.
$$$^{\text{†}}$$$Медиана массива нечётной длины $$$x$$$ — это $$$\lceil\frac{x}{2}\rceil$$$-й элемент массива после сортировки по неубыванию.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n \lt 5000$$$, $$$n$$$ нечётно) — длину массива $$$a$$$.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$5000^2$$$.
Для каждого набора входных данных выведите одно целое число — максимальное количество подмассивов.
1053 3 2 4 379 5 7 7 4 7 791 1 1 1 1 1 1 1 11531 2 332 2 251 2 3 4 552 1 3 2 272 2 1 2 3 2 292 1 2 3 2 1 2 3 2
3391131355
В первом наборе входных данных оптимально разбить $$$a$$$ на $$$[\underline 3, \underline 3, \underline{2, 4, 3}]$$$.
Во втором наборе входных данных оптимально разбить $$$a$$$ на $$$[\underline{9, 5, 7}, \underline 7, \underline{4, 7, 7}]$$$.
В третьем наборе входных данных, поскольку все элементы одинаковы, можно выделить каждый элемент в отдельный подмассив.
