Description

1. Add one person to the left or right end (their clothing color can be chosen as needed).
2. Insert one person between any two adjacent people (their clothing color can be chosen as needed).
3. Remove one person.
4. Change one person's clothing color.

The teacher wants to know, for the current lineup, the minimum number of adjustments needed. Please write a program to answer this.

Because joining the chorus is very popular, you may assume there is an unlimited number of people available, i.e., you can always add someone when needed. Clothing colors can be chosen arbitrarily as well.

Input Format

The first line contains an integer $n$ ($1 \le n \le 3000$).

The second line contains $n$ integers, from left to right, representing the current clothing color ID of each member, all integers from $1$ to $3000$.

Output Format

Output a single number: the minimum number of adjustments needed to make the lineup meet the requirement.

5
1 2 2 4 3

2

Hint

Translated by ChatGPT 5