まず、問題に対する重要な観察として、以下が挙げられます。

• 全ての整数 \(i\) (\(1 \le i \le N\)) について、もし \(A_i \neq A_{N+1-i}\) ならば、整数 \(A_i\) と整数 \(A_{N+1-i}\) は最終的に同じ整数に置換されていなければならない。

このことを無向グラフの頂点 \(A_i,A_{N+1-i}\) を結ぶ辺として表します。

すると、以下のことがわかります。

• 全ての整数組 \((i,j)\) について、もし、頂点 \(i\) と頂点 \(j\) がグラフの同じ連結成分に属していた場合、 \(i\) と \(j\) とは最終的に同じ整数に置換されていなければならない。

では、あるひとつの連結成分に含まれる整数を、最小の操作回数で全て同じにするにはどのようにすればよいのでしょうか?

あるひとつの連結成分に整数が \(k\) 個含まれている場合、明らかに、それらを同じ整数に置換するためには \(k-1\) 回以上の操作が必要です。逆に、以下のように置換することで、 \(k-1\) 回の操作回数を達成できます。

連結成分に含まれる整数を \(1\) つ選び、連結成分に含まれる他の整数を全て、選んだ整数に順に置換していく。

以上より、この問題の解は、 (\(A\) に含まれる整数の種類数) - (グラフの連結成分の個数) となります。

これを求める方法はいくつかありますが、主に以下の \(2\) つが考えられます。

• 連結成分ごとに、DFS(深さ優先探索)やBFS(幅優先探索)を行う。
• 素集合データ構造(Union-Find)を使う。

計算量は \(O(N)\) から \(O(N \log N)\) 程度となり、この問題を解くのに十分高速です。

#include<bits/stdc++.h>

using namespace std;
using Graph=vector<vector<int>>;

void dfs(int v,vector<bool> &flag,Graph &g){
  if(!flag[v]){return;}
  flag[v]=false;
  for(auto &nx : g[v]){dfs(nx,flag,g);}
}

int main(){
  int n,res=0;
  cin >> n;
  vector<int> a(n);
  vector<bool> flag(200005,false);
  Graph g(200005);
  for(auto &nx : a){
    cin >> nx;
    if(!flag[nx]){flag[nx]=true;res++;}
  }
  int p=0,q=n-1;
  while(p<q){
    g[a[p]].push_back(a[q]);
    g[a[q]].push_back(a[p]);
    p++;q--;
  }
  for(int i=1;i<=200000;i++){
    if(flag[i]){
      res--;
      dfs(i,flag,g);
    }
  }
  cout << res << '\n';
}