Minimum Operations to Empty the Sequence

You are given a sequence of n integers \(a_1, a_2, \dots, a_n\). You need to apply a series of operations to completely remove all elements from the sequence. There are two types of operations:

1. Swap Operation: Choose two indices \(i, j\) such that \(1 \le i < j \le n\) and swap \(a_i\) and \(a_j\). This operation costs 1.
2. Deletion Operation: Choose indices \(i, j\) such that \(1 \le i \le j \le n\) and \(a_i = a_j\), and then remove the entire contiguous segment \(a_i, a_{i+1}, \dots, a_j\) from the sequence. This operation also costs 1.

Your goal is to remove all elements from the sequence with a minimum total number of operations (the sum of swap and deletion operations). Note that before each deletion operation the sequence is re-indexed from 1 to its current length. You are allowed to perform the operations in any order.

Hint (for implementation): It can be shown that a dynamic programming approach using a state \(dp[i][j]\) representing the minimum operations required to remove the subarray \(a_i, a_{i+1}, \dots, a_j\) works. A recurrence for the interval \([i, j]\) can be formulated as follows:

[ \begin{aligned} &dp(i,j) = 0 \quad &\text{if } i > j,\ &dp(i,i) = 1,\ &dp(i,j) = \min \Bigl{ dp(i+1,j) + 1,\ &\quad\quad\quad dp(i,j-1) + 1,\ &\quad\quad\quad dp(i+1,j-1) + \begin{cases} 0, &\text{if } a_i = a_j, \ 1, &\text{if } a_i \neq a_j,\end{cases} \Bigr} \end{aligned} ]

This recurrence takes into account the possibility of deleting single elements as well as pairing endpoints. The term \(dp(i+1,j-1)\) can be used directly if \(a_i = a_j\); otherwise a swap operation (costing 1) can be performed to effectively pair the endpoints.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 1000\)) representing the length of the sequence.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\), where \(1 \le a_i \le 10^9\).

outputFormat

Output a single integer, the minimum number of operations (swaps and deletions) required to remove all elements from the sequence.

sample

3
1 2 1

1