AT_abc397_f [ABC397F] Variety Split Hard

> この問題は 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}) $ のそれぞれに含まれる整数の種類数の和としてありえる最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

答えを出力せよ。

### Sample Explanation 1 $ (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 $ になります。 ### Constraints - $ 3 \leq N \leq 3 \times 10^5 $ - $ 1 \leq A_i \leq N $ ( $ 1 \leq i \leq N $ ) - 入力はすべて整数である