← 返回题目列表

Codeforces · 1630/C

C. 画中间

中文机器翻译题面 查看原题

给定 $$$n$$$ 个元素,编号从 $$$1$$$ 到 $$$n$$$,元素 $$$i$$$ 具有值 $$$a_i$$$ 和颜色 $$$c_i$$$,最初,对于所有 $$$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

注意

在第一个测试中,可以按顺序应用以下操作: