Maximum Length of Special Array After Removal

We call an array special if all its elements are pairwise distinct. You are given an array $$ (a_1, a_2, \cdots, a_n) $$ of length n. You are allowed to perform exactly one operation: choose two indices L and R with 1 \le L \le R \le n and remove the contiguous subarray $$ (a_L, a_{L+1}, \cdots, a_R) $$ from the array. The remaining array is the concatenation of the prefix (if any) and the suffix (if any).

The task is to maximize the length of the resulting special array (i.e. an array in which all elements are distinct). Note that you must remove at least one element. For example, if the original array is already special, you cannot choose to remove an empty segment and must remove at least one element.

Input Example: For the array [1, 2, 3, 4], even though the entire array is distinct, you have to remove at least one element. The maximum length of a special array you can obtain is 3.

inputFormat

The first line contains an integer n (1 \le n \le 2000), the number of elements in the array.

The second line contains n integers a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9), representing the array.

outputFormat

Output a single integer — the maximum possible length of the resulting special array after performing exactly one removal operation.

sample

4
1 2 3 4

3