/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
この問題は F 問題の簡易版です。
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A を 1 か所で区切って 2 個の空でない連続する部分列に分割するとき、数列に含まれる数の種類数の和としてありえる最大値を求めてください。
より厳密には、1 \leq i \leq N-1 を満たす整数 i について (A_1,A_2,\ldots,A_i), (A_{i+1},A_{i+2},\ldots,A_N) のそれぞれに含まれる整数の種類数の和としてありえる最大値を求めてください。
制約
- 2 \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=1 としたとき、(3) と (1,4,1,5) のそれぞれに含まれる整数の種類数は 1,3 で、これらの和は 4 です。
- i=2 としたとき、(3,1) と (4,1,5) のそれぞれに含まれる整数の種類数は 2,3 で、これらの和は 5 です。
- i=3 としたとき、(3,1,4) と (1,5) のそれぞれに含まれる整数の種類数は 3,2 で、これらの和は 5 です。
- i=4 としたとき、(3,1,4,1) と (5) のそれぞれに含まれる整数の種類数は 3,1 で、これらの和は 4 です。
よって、 i=2,3 のときに、最大値 5 を取ります。
入力例 2
10 2 5 6 5 2 1 7 9 7 2
出力例 2
8
Score : 350 points
Problem Statement
This problem is a simplified version of Problem F.
You are given an integer sequence of length N: A = (A_1, A_2, \ldots, A_N).
When splitting A at one position into two 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 two values for an integer i such that 1 \leq i \leq N-1: the count of distinct integers in (A_1, A_2, \ldots, A_i), and the count of distinct integers in (A_{i+1}, A_{i+2}, \ldots, A_N).
Constraints
- 2 \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
- For i=1, (3) contains 1 distinct integer, and (1,4,1,5) contains 3 distinct integers, for a total of 4.
- For i=2, (3,1) contains 2 distinct integers, and (4,1,5) contains 3 distinct integers, for a total of 5.
- For i=3, (3,1,4) contains 3 distinct integers, and (1,5) contains 2 distinct integers, for a total of 5.
- For i=4, (3,1,4,1) contains 3 distinct integers, and (5) contains 1 distinct integer, for a total of 4.
Therefore, the maximum sum is 5 for i=2,3.
Sample Input 2
10 2 5 6 5 2 1 7 9 7 2
Sample Output 2
8