← 返回题目列表

AtCoder · abc206_d

D. 回文

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个序列 N 正整数: A=(A_1,A_2, \dots A_N)。 您可以执行零次或多次以下的操作。至少需要多少次操作才能完成 A 回文?

  • 选择一对 (x,y) 正整数,并替换每次出现的 x in A 与 y.

在这里,我们说 A 是回文当且仅当 A_i=A_{N+1-i} 对于每个都成立 i (1 \le i \le N).

约束

  • 输入中的所有值都是整数。
  • 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).
  • 替换每次出现的 3 in A 与 2,我们有 A=(1,5,2,2,5,2,2,1).
  • 替换每次出现的 2 in A 与 5,我们有 A=(1,5,5,5,5,5,5,1).

这样,我们可以使 A 两次操作中的回文,这是最少需要的。


示例输入 2

7
1 2 3 4 1 2 3

示例输出 2

1

示例输入 3

1
200000

示例输出 3

0

A 一开始可能已经是回文。