分数: 350 点
问题陈述
这个问题是问题F的简化版本。
给定一个长度为的整数序列 N: A = (A_1, A_2, \ldots, A_N).
分割时 A 在两个非空(连续)子数组的一个位置,找到这些子数组中不同整数计数的最大可能总和。
更正式地说,找到一个整数的以下两个值的最大和 i 这样 1 \leq i \leq N-1: 中不同整数的计数 (A_1, A_2, \ldots, A_i),以及不同整数的计数 (A_{i+1}, A_{i+2}, \ldots, A_N).
约束
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq N (1 \leq i \leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印答案。
示例输入 1
5 3 1 4 1 5
示例输出 1
5
- 对于 i=1, (3) 包含 1 不同的整数,以及 (1,4,1,5) 包含 3 不同的整数,总共 4.
- 对于 i=2, (3,1) 包含 2 不同的整数,以及 (4,1,5) 包含 3 不同的整数,总共 5.
- 对于 i=3, (3,1,4) 包含 3 不同的整数,以及 (1,5) 包含 2 不同的整数,总共 5.
- 对于 i=4, (3,1,4,1) 包含 3 不同的整数,以及 (5) 包含 1 不同的整数,总共 4.
因此,最大总和为 5 为 i=2,3.
示例输入 2
10 2 5 6 5 2 1 7 9 7 2
示例输出 2
8