Codeforces Round 804 (Div. 2) |
---|
Закончено |
Вам дано целое число $$$n$$$ и массив целых чисел $$$a_1,a_2,\ldots,a_n$$$.
За одну операцию вы можете выбрать индекс $$$i$$$ ($$$1 \le i \lt n$$$), для которого $$$a_i \neq a_{i+1}$$$, и удалить оба элемента $$$a_i$$$ и $$$a_{i+1}$$$ из массива. После удаления $$$a_i$$$ и $$$a_{i+1}$$$ оставшиеся части массива соединяются.
Например, если $$$a=[1,4,3,3,6,2]$$$, то после применения операции с $$$i=2$$$ получившийся массив будет равен $$$[1,3,6,2]$$$.
Какова максимальная возможная длина массива из равных элементов, который можно получить из $$$a$$$ применением нескольких (возможно, нуля) операций, описанных выше?
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 5000$$$) — длина массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10\,000$$$.
Для каждого набора входных данных выведите единственное целое число — максимальную возможную длину массива из равных элементов, который можно получить из $$$a$$$ применением некоторой последовательности операций.
571 2 3 2 1 3 31161 1 1 2 2 281 1 2 2 3 3 1 1121 5 2 3 3 3 4 4 4 4 3 3
3 1 0 4 2
Для первого набора входных данных оптимальной последовательностью операций будет: $$$[1,2,3,2,1,3,3] \rightarrow [3,2,1,3,3] \rightarrow [3,3,3]$$$.
Во втором наборе входных данных все элементы массива уже равны.
В третьем наборе входных данных единственной возможной последовательностью операций является: $$$[1,1,1,2,2,2] \rightarrow [1,1,2,2] \rightarrow [1,2] \rightarrow []$$$. Обратите внимание, что по условию два удаляемых элемента должны быть различны.
В четвёртом наборе входных данных оптимальной последовательностью является: $$$[1,1,2,2,3,3,1,1] \rightarrow [1,1,2,3,1,1] \rightarrow [1,1,1,1]$$$.
В пятом наборе входных данных единственным массивом из двух равных элементов, который можно получить, является $$$[4,4]$$$.
Название |
---|