/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 項からなる正整数列 A=(A_1,A_2, \dots A_N) が与えられます。
以下の操作を 0 回以上何度でも行える時、操作を最小何回行えば、A を回文にすることができますか？
- ある正整数の組 (x,y) を選ぶ。その後、現在 A に含まれる x をすべて y に置き換える。
なお、この問題では、全ての整数 i (1 \le i \le N) について、A_i=A_{N+1-i} が成り立つとき、またその時に限って、A が回文であると言います。
制約
- 入力は全て整数
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 2 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
8 1 5 3 2 5 2 3 1
出力例 1
2
- はじめ、A=(1,5,3,2,5,2,3,1) です。
- A に含まれる 3 を全て 2 に置き換えると、A=(1,5,2,2,5,2,2,1) となります。
- A に含まれる 2 を全て 5 に置き換えると、A=(1,5,5,5,5,5,5,1) となります。
以上の操作を行うと、A を 2 回の操作で回文にすることができ、これが最小です。
入力例 2
7 1 2 3 4 1 2 3
出力例 2
1
入力例 3
1 200000
出力例 3
0
A がはじめから回文である可能性もあります。
Score : 400 points
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.