Дано \(n\) элементов, пронумерованных от \(1\) до \(n\). Элемент \(i\) имеет значение \(a_i\) и цвет \(c_i\). Изначально \(c_i = 0\) для всех \(i\).
Можно выполнять следующую операцию:
- Выбрать три элемента \(i\), \(j\) и \(k\) (\(1 \leq i < j < k \leq n\)) такие, что \(c_i\), \(c_j\) и \(c_k\) равны \(0\) и \(a_i = a_k\), и затем присвоить \(c_j = 1\).
Найдите максимальное значение \(\sum\limits_{i=1}^n{c_i}\), которое можно получить, выполнив описанную операцию некоторое (любое) количество раз.
Выходные данные
Напечатайте одно целое число — максимальное значение \(\sum\limits_{i=1}^n{c_i}\), которое можно получить, выполнив описанную операцию некоторое (любое) количество раз.
Примечание
В первом примере одним из возможных решений является выполнение следующих операций:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1 2 1 2 7 4 7
|
2
|
|
2
|
13
1 2 3 2 1 3 3 4 5 5 5 4 7
|
7
|