F2 - Full Color[Hard]

2 secs 1024 MB
Machonium

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

問題文


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

として,下記の制約下で答えを求めてください。

  • 入力はすべて整数である

サンプル


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

提出


Go (1.14)