题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,...,A_N)$。你要把 $A$ 分成连续的两段。

形式上，你要选择一个整数 $i$ 满足 $1≤i≤N$，然后把 $A$ 分成 $(A_1,A_2,...,A_i)$ 和 $(A_{i+1},A_{i+2},...,A_N)$ 这两部分。

设 $x$ 为 $(A_1,A_2,...,A_i)$ 中不同整数的个数，$y$ 为 $(A_{i+1},A_{i+2},...,A_N)$ 中不同整数的个数，你想要让 $x+y$ 最大。求出这个最大值。

输入格式

第一行一个正整数 $N$，表示序列 $A$ 的长度。

第二行 $N$ 个整数 $A_1,A_2,...,A_N$，表示序列 $A$。

输出格式

输出 $x+y$ 的最大值。

5
3 1 4 1 5

5

• $i = 1$ 时，$A$ 被分成了 $(3)$ 和 $(1, 4, 1, 5)$，此时 $x = 1, y = 3, x + y = 4$。
• $i = 2$ 时，$A$ 被分成了 $(3, 1)$ 和 $(4, 1, 5)$，此时 $x = 2, y = 3, x + y = 5$。
• $i = 3$ 时，$A$ 被分成了 $(3, 1, 4)$ 和 $(1, 5)$，此时 $x = 3, y = 2, x + y = 5$。
• $i = 4$ 时，$A$ 被分成了 $(3, 1, 4, 1)$ 和 $(5)$，此时 $x = 3, y = 1, x + y = 4$。 综上所述，$x + y$ 的最大值为 $5$。

10
2 5 6 5 2 1 7 9 7 2

8

数据范围/提示

对于所有的数据，$2≤N≤3×10^5$，$1≤A_i≤N$。