Вам дано целое число \(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\) применением нескольких (возможно, нуля) операций, описанных выше?
Примечание
Для первого набора входных данных оптимальной последовательностью операций будет: \([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]\).