考えたこと
- $A$を両端から，ペアとなる文字を中心に向かって順に見ていく．
- もし「異なる」場合は，その時点で置き換える．
ここで問題になるのは，ある2つの数字を等しいとみなす処理を繰り返すため，「数字が異なる」という状態が変わっていってしまうこと．これは，Union-Findで同じとみなした数字をグループ化していくことで管理できる．
Union-Findは，例えば次のページからコピペできる．
PythonでのUnion-Find（素集合データ構造）の実装と使い方 | note.nkmk.me
今回は，次を使えば良い．初期化時に要素数が足りないとREするので注意．
uf = UnionFind(2 * (10 ** 5) + 1)uf.same(x, y)uf.union(x, y)
Union-Find以外の部分は以下：
N = int(input()) A = list(map(int, input().split())) uf = UnionFind(2 * (10 ** 5) + 1) ans = 0 for i in range(N // 2 + 1): x, y = A[i], A[N - 1 - i] if not uf.same(x, y): ans += 1 uf.union(x, y) print(ans)
