AT_abc397_f.[ABC397F] Variety Split Hard

本题是 C 题的强化版，分割个数变为 $3$ 个。

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$。

当在 $A$ 的两个位置将其分割为 $3$ 个非空的连续子序列时，求这三个子序列中不同整数的种类数之和的最大可能值。

更严格地说，对于满足 $1 \leq i < j \leq N-1$ 的整数对 $(i, j)$，分别计算子序列 $(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)$ 中不同整数的种类数之和，并求这些和的最大值。

输入通过标准输入给出，格式如下：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出答案。

约束条件

• $3 \leq N \leq 3 \times 10^5$
• $1 \leq A_i \leq N$ ($1 \leq i \leq N$)
• 输入均为整数

样例解释 1

当 $(i, j) = (2, 4)$ 时，分割为 $(3, 1)$、$(4, 1)$ 和 $(5)$ 这三个连续子序列，各自的种类数分别为 $2, 2, 1$，和为 $5$。由于无法得到比 $5$ 更大的值，因此答案是 $5$。其他如 $(i, j) = (1, 3)$、$(2, 3)$、$(3, 4)$ 等情况也能得到和为 $5$。

翻译由 DeepSeek R1 完成