Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов.
Палиндромная последовательность — это последовательность, которая равна перевернутой себе.
Задана последовательность из \(n\) целых чисел \(a_1, a_2, \dots, a_n\). Любое целое значение встречается в \(a\) не более двух раз.
Какова длина самой длинной палиндромной подпоследовательности последовательности \(a\)?
Выходные данные
На каждый набор входных данных выведите одно целое число — длину самой длинной палиндромной подпоследовательности последовательности \(a\).
Примечание
Вот самые длинные палиндромные подпоследовательности для наборов входных данных из примера:
- 2 1 3 1 5 2
- 1 3 3 4 4 1 или 1 3 3 4 4 1
- 1
- 1 1
- 4 4 2 5 7 2 3 или 4 4 2 5 7 2 3
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
6
2 1 3 1 5 2
6
1 3 3 4 4 1
1
1
2
1 1
7
4 4 2 5 7 2 3
|
5
4
1
2
3
|