C. Раскрась середину
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано $$$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}$$$, которое можно получить, выполнив описанную операцию некоторое (любое) количество раз.

Входные данные

Первая строка содержит целое число $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — количество элементов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — где $$$a_i$$$ равно значению $$$i$$$-го элемента.

Выходные данные

Напечатайте одно целое число — максимальное значение $$$\sum\limits_{i=1}^n{c_i}$$$, которое можно получить, выполнив описанную операцию некоторое (любое) количество раз.

Примеры
Входные данные
7
1 2 1 2 7 4 7
Выходные данные
2
Входные данные
13
1 2 3 2 1 3 3 4 5 5 5 4 7
Выходные данные
7
Примечание

В первом примере одним из возможных решений является выполнение следующих операций: