F2 - Full Color[Hard]

2 secs 1024 MB
Machonium's icon Machonium

問題 F1 とは制約のみが異なります

問題文

F1 - Full Color と同じ状況を考えます

K=4×105K = 4 \times 10^5 として,下記の制約下で答えを求めてください。

  • 1N,Ci4×105(1iN)1 \leq N, C_i \leq \bold{4 \times 10^5} \scriptsize \hspace{0.3em} (1 \leq i \leq N)
  • 入力はすべて整数である

サンプル

F1 と同一のものです.

入力例1
5
1 2 3 4 2
出力例1
4

入力例2
13
3 1 8 3 3 4 8 8 3 1 8 1 3
出力例2
3

Submit


Go (1.21)