题目描述

给定长度为 $N$ 的整数序列 $A$。

你要选择一个位置，把序列分成左右两个非空连续部分。求左右两部分中不同整数个数之和的最大值。

输入格式

第一行输入 $N$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出最大值。

样例

5
3 1 4 1 5

5

10
2 5 6 5 2 1 7 9 7 2

8

2
1 1

2

样例说明

在样例 $1$ 中，可以在第 $3$ 个元素后分割。左侧序列 $3,1,4$ 中有 $3$ 种不同整数，右侧序列 $1,5$ 中有 $2$ 种，总和为 $5$。

在样例 $2$ 中，选择合适的分割位置后，左右两部分中不同整数个数之和最大为 $8$。

数据范围

• 对于 $50\%$ 的数据，$2\le N\le1000$；
• 对于 $100\%$ 的数据，$2\le N\le3\times10^5$，$1\le A_i\le N$。