题目描述

给定一个长度为 $N$ 的整数列 $A=(A_1, A_2, \ldots, A_N)$。

当在 $A$ 的某一位置将其分割为 $2$ 个非空的连续子序列时，求这两个子序列中不同整数的种类数之和的最大可能值。

更严格地说，对于满足 $1 \leq i \leq N-1$ 的整数 $i$，分别计算子序列 $(A_1, A_2, \ldots, A_i)$ 和 $(A_{i+1}, A_{i+2}, \ldots, A_N)$ 中不同整数的种类数之和，并求这些和的最大值。

输入格式

输入通过标准输入给出，格式如下：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

5
3 1 4 1 5

输出 #1

5

输入输出样例 #2

输入 #2

10
2 5 6 5 2 1 7 9 7 2

输出 #2

8

样例解释 1

• 当 $i=1$ 时，子序列 $(3)$ 和 $(1,4,1,5)$ 各自包含的整数种类数分别为 $1$ 和 $3$，和为 $4$。
• 当 $i=2$ 时，子序列 $(3,1)$ 和 $(4,1,5)$ 各自包含的整数种类数分别为 $2$ 和 $3$，和为 $5$。
• 当 $i=3$ 时，子序列 $(3,1,4)$ 和 $(1,5)$ 各自包含的整数种类数分别为 $3$ 和 $2$，和为 $5$。
• 当 $i=4$ 时，子序列 $(3,1,4,1)$ 和 $(5)$ 各自包含的整数种类数分别为 $3$ 和 $1$，和为 $4$。

因此，当 $i=2$ 或 $i=3$ 时，取到最大值 $5$。

限制与约定

对于 $40\%$ 的数据，$2 \leq N \leq 100$

对于 $100\%$ 的数据， $2 \leq N \leq 3 \times 10^5$ $1 \leq A_i \leq N$ ($1 \leq i \leq N$) 输入均为整数

• 时间限制: $1 s$
• 空间限制: $256 MB$