/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
この問題は C 問題の強化版です。分割する個数が 3 個になります。
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A を 2 か所で区切って 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}) のそれぞれに含まれる整数の種類数の和としてありえる最大値を求めてください。
制約
- 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) の 3 つの連続する部分列に分割すると、それぞれに含まれる整数の種類数は 2,2,1 でこれらの和は 5 です。また、5 より大きい値は取り得ないので、答えは 5 です。他にも、(i,j)=(1,3),(2,3),(3,4) などでも種類数の和は 5 になります。
入力例 2
10 2 5 6 4 4 1 1 3 1 4
出力例 2
9
Score : 550 points
Problem Statement
This problem is a harder version of Problem C. Here, the sequence is split into three subarrays.
You are given an integer sequence of length N: A = (A_1, A_2, \ldots, A_N).
When splitting A at two positions into three non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.
More formally, find the maximum sum of the following three values for a pair of integers (i,j) such that 1 \leq i < j \leq N-1: the count of distinct integers in (A_1, A_2, \ldots, A_i), the count of distinct integers in (A_{i+1},A_{i+2},\ldots,A_j), and the count of distinct integers in (A_{j+1},A_{j+2},\ldots,A_{N}).
Constraints
- 3 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq N (1 \leq i \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
5 3 1 4 1 5
Sample Output 1
5
If we let (i,j) = (2,4) to split the sequence into three subarrays (3,1), (4,1), (5), the counts of distinct integers in those subarrays are 2, 2, 1, respectively, for a total of 5. This sum cannot be greater than 5, so the answer is 5. Other partitions, such as (i,j) = (1,3), (2,3), (3,4), also achieve this sum.
Sample Input 2
10 2 5 6 4 4 1 1 3 1 4
Sample Output 2
9