← 返回题目列表

AtCoder · abc397_f

I. 各种分裂硬

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

分数: 550 点

问题陈述

这个问题是问题 C 的更难版本。这里,序列被分成三个子数组。

给你一个长度的整数序列 N: A = (A_1, A_2, \ldots, A_N).

分割时 A 在三个非空(连续)子数组中的两个位置,找到这些子数组中不同整数的计数的最大可能总和。

更正式地说,找到一对整数的以下三个值的最大和 (i,j) 这样 1 \leq i < j \leq N-1: 中不同整数的计数 (A_1, A_2, \ldots, A_i),不同整数的计数 (A_{i+1},A_{i+2},\ldots,A_j),以及中不同整数的计数 (A_{j+1},A_{j+2},\ldots,A_{N}).

约束

  • 3 \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,j) = (2,4) 将序列拆分为三个子数组 (3,1), (4,1), (5),这些子数组中不同整数的计数是 2, 2, 1分别为总共 5。该总和不能大于 5,所以答案是 5。其他分区,例如 (i,j) = (1,3), (2,3), (3,4),也达到这个和。


示例输入 2

10
2 5 6 4 4 1 1 3 1 4

示例输出 2

9