← 返回题目列表

AtCoder · abc397_c

F. 品种拆分容易

中文机器翻译题面 查看原题

分数: 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