Enjoy erasing Tenzing, identified as Accepted!
У Тенцинга есть \(n\) шариков, расположенных в один ряд. Цвет \(i\)-го шарика слева — \(a_i\).
Тенцинг может проделать следующую операцию любое количество раз:
- выбрать \(i\) и \(j\) такие, что \(1\leq i < j \leq |a|\) и \(a_i=a_j\),
- удалить из массива \(a_i,a_{i+1},\ldots,a_j\) (и уменьшить индексы всех элементов справа от \(a_j\) на \(j-i+1\)).
Тенцинг хочет узнать максимальное количество шариков, которое он может удалить.
Выходные данные
Для каждого набора входных данных выведите максимальное количество шариков, которые может удалить Тенцинг.
Примечание
В первом примере Тенцинг выберет \(i=2\) и \(j=3\) в первой операции так, что \(a=[1,3,3]\). Затем Тенцинг снова выберет \(i=2\) и \(j=3\) во второй операции так, что \(a=[1]\). Таким образом, Тенцинг может удалить в общей сложности \(4\) шарика.
Во втором примере Тенцинг выберет \(i=1\) и \(j=3\) в первой и единственной операции так, что \(a=[2]\). Таким образом, Тенцинг может удалить \(3\) шарика.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5
1 2 2 3 3
4
1 2 1 2
|
4
3
|