Paint the Middle

题意翻译

给定 $n$ 个元素，第 $i$ 个元素有一个值 $a_i$ 和一个颜色 $c_i$，初始时，$a_i$ 在输入中给定，$c_i=0$。你可以执行若干次操作，每次操作你可以选择满足 $1\leqslant i<j<k\leqslant n$，$c_i=c_j=c_k=0$ 且 $a_i=a_k$ 的三个位置 $i,j,k$，然后将 $c_j$ 变为 $1$。你希望最大化 $\sum\limits_{i=1}^n c_i$ 的值，求这个最大值。 数据范围： - $3\leqslant n\leqslant 2\times 10^5$。 - $1\leqslant a_i\leqslant n$。 Translated by Eason_AC 2022.1.28

题目描述

You are given $ n $ elements numbered from $ 1 $ to $ n $ , the element $ i $ has value $ a_i $ and color $ c_i $ , initially, $ c_i = 0 $ for all $ i $ . The following operation can be applied: - Select three elements $ i $ , $ j $ and $ k $ ( $ 1 \leq i < j < k \leq n $ ), such that $ c_i $ , $ c_j $ and $ c_k $ are all equal to $ 0 $ and $ a_i = a_k $ , then set $ c_j = 1 $ . Find the maximum value of $ \sum\limits_{i=1}^n{c_i} $ that can be obtained after applying the given operation any number of times.

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 3 \leq n \leq 2 \cdot 10^5 $ ) — the number of elements. The second line consists of $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq n $ ), where $ a_i $ is the value of the $ i $ -th element.

输出格式

Print a single integer in a line — the maximum value of $ \sum\limits_{i=1}^n{c_i} $ that can be obtained after applying the given operation any number of times.

输入输出样例

输入样例 #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

说明

In the first test, it is possible to apply the following operations in order: