AT_abc397_f [ABC397F] Variety Split Hard

[problemUrl]: https://atcoder.jp/contests/abc397/tasks/abc397_f > 本题是 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 完成