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

問題文

$1$ から $N$ までの番号がついた $N$ 個の電球が，番号の昇順に一列に並います。
それぞれの電球は，色 $1$ から色 $K$ までのいずれかの色をもっており，種類は色のみによって区別がつけられています。
$i \scriptsize \hspace{0.3em} (1 \leq i \leq N)$ 番目の電球の色は色 $C_i$ です。

幕田元くんは区間を一つ選び，その区間に含まれる電球をすべて購入します。
より厳密には，$2$ 整数 $l,r \scriptsize \hspace{0.2em} (1 \leq l \leq r \leq N)$ を選び，番号が閉区間 $[l, r]$ に含まれる電球をすべて購入します。

ただし，区間に含まれる電球の色が重複してはいけません。

ここでは $K = 3000$ とします。
幕田元くんは最大で何種類の電球を購入することができるか求めてください。

制約

• $1 \leq N, C_i \leq 3000 \scriptsize \hspace{0.3em} (1 \leq i \leq N)$
• 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル

5
1 2 3 4 2

4

区間 $[1, 4]$ を選ぶと，$1, 2, 3, 4$ 番の $4$ 種類の電球を色が重複しないように購入することができます。
他のどのような区間を選んで電球を購入しても，$4$ 種類より多い種類の電球を購入することはできません。

13
3 1 8 3 3 4 8 8 3 1 8 1 3

3

区間 $[1, 3], [2, 4], [5, 7], [8, 10], [9, 11], [11, 13]$ を選ぶと，$3$ 種類の電球を購入することができます。
たとえば区間 $[2, 6]$ には $4$ 種類の電球が含まれますが，色 $3$ をもった電球が重複してしまうので，購入することはできません。