Score : $400$ points

问题陈述

给定一个包含 $N$ 个正整数的序列：$A=(A_1,A_2, \dots A_N)$。你可以执行零次或多次以下操作。至少需要多少次操作才能使 $A$ 变为回文序列？

• 选择一对正整数 $(x,y)$，并在 $A$ 中用 $y$ 替换所有出现的 $x$。

这里我们说 $A$ 是回文序列，当且仅当对于每个 $i$（$1 \le i \le N$），满足 $A_i=A_{N+1-i}$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a sequence of $N$ positive integers: $A=(A_1,A_2, \dots A_N)$. You can do the operation below zero or more times. At least how many operations are needed to make $A$ a palindrome?

• Choose a pair $(x,y)$ of positive integers, and replace every occurrence of $x$ in $A$ with $y$.

Here, we say $A$ is a palindrome if and only if $A_i=A_{N+1-i}$ holds for every $i$ ($1 \le i \le N$).

Constraints

• All values in input are integers.
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 2 \times 10^5$

Input

Input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answer as an integer.

Sample Input 1

8
1 5 3 2 5 2 3 1

Sample Output 1

2

• Initially, we have $A=(1,5,3,2,5,2,3,1)$.
• After replacing every occurrence of $3$ in $A$ with $2$, we have $A=(1,5,2,2,5,2,2,1)$.
• After replacing every occurrence of $2$ in $A$ with $5$, we have $A=(1,5,5,5,5,5,5,1)$.

In this way, we can make $A$ a palindrome in two operations, which is the minimum needed.

Sample Input 2

7
1 2 3 4 1 2 3

Sample Output 2

1

Sample Input 3

1
200000

Sample Output 3

0

$A$ may already be a palindrome in the beginning.

update @ 2024/3/10 09:19:31