涂色中间元素

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定 $n$ 个元素，编号从 $1$ 到 $n$，第 $i$ 个元素的值为 $a_i$，颜色为 $c_i$，初始时所有 $c_i = 0$。

可以进行如下操作：

• 选择三个元素 $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}$ 的最大值。

样例输入 1

7
1 2 1 2 7 4 7

样例输出 1

2

样例输入 2

13
1 2 3 2 1 3 3 4 5 5 5 4 7

样例输出 2

7

提示

在第一个测试样例中，可以按如下顺序进行操作：

数据范围