Background

At the school's arts festival, the chorus is required to compete, and the colors of the members' clothes must not be chaotic: the chorus members should stand in a single row, and the clothing colors must be left-right symmetric.

For example: "red blue green blue red" or "red blue green green blue red" are acceptable, while "red blue green red" or "blue green blue red" are not.

The chorus can be quite large, with up to $3000$ students. The teacher wants to adjust the lineup to meet the requirement with as few adjustments as possible. Each of the following actions counts as one adjustment:

Problem 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