给定 $$$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
注意
在第一个测试中,可以按顺序应用以下操作: