P17828 [CSP-J 2026] 回文串 / string（民间数据）

小 R 有一个长度为 $L$ 的字符串 $S=s_1\ldots s_L$，其中只包含小写英文字母。小 R 发现，虽然 $S$ 可能很长，但它可以分成 $n$ 个连续的段，其中第 $i\ (1\le i\le n)$ 段由 $a_i$ 个小写英文字母 $c_i$ 构成。把这 $n$ 段依次拼接起来便得到 $S$，因此 $L=\sum_{i=1}^{n}a_i$。相邻两段中的字符可以相同。 小 X 喜欢回文串。若一个字符串反转后与原字符串相同，就称它是回文串，例如 `aba`、`abba` 都是回文串，而 `aabbc` 不是。也就是说，字符串 $S$ 是回文串，当且仅当对于所有 $i\ (1\le i\le L)$，均有 $s_i=s_{L+1-i}$。 小 X 想让小 R 把 $S$ 改成回文串。小 R 可以将 $S$ 中任意一个位置的字符修改成任意小写英文字母。他想用尽量少的修改满足小 X 的要求。 你需要帮助小 R 求出，他最少需要修改多少个位置的字符，才能将 $S$ 改成回文串。

从文件 `string.in` 中读入数据。 输入的第一行包含一个正整数 $n$。 输入的第 $i+1\ (1\le i\le n)$ 行包含一个正整数 $a_i$ 和一个小写英文字母 $c_i$。

输出到文件 `string.out` 中。 输出一行一个整数，表示小 R 最少需要修改多少个位置的字符，才能将 $S$ 改成回文串。

### 样例 1 解释 小 R 的字符串 $S$ 由 $3$ 段构成：第 $1$ 段由 $2$ 个 `a` 组成，第 $2$ 段由 $2$ 个 `b` 组成，第 $3$ 段由 $1$ 个 `c` 组成，依次拼接得到 $S=\mathtt{aabbc}$。 小 R 可以将最后一个字符 `c` 和倒数第二个字符 `b` 都改为 `a`，得到回文串 `aabaa`，共修改 $2$ 个位置的字符。可以证明，小 R 最少需要修改 $2$ 个位置的字符，才能将 $S$ 改成回文串。 ### 样例 2 解释 小 R 的字符串 $S$ 由 $2$ 段构成：第 $1$ 段由 $2$ 个 `a` 组成，第 $2$ 段由 $3$ 个 `a` 组成，依次拼接得到 $S=\mathtt{aaaaa}$，则 $S$ 已经是回文串，不需要修改。 ### 样例 4 见题目目录下的 `string/4.in` 与 `string/4.ans`。 该样例满足测试点 $10\sim12$ 的约束条件。 ### 样例 5 见题目目录下的 `string/5.in` 与 `string/5.ans`。 该样例满足测试点 $13\sim16$ 的约束条件。 ### 样例 6 见题目目录下的 `string/6.in` 与 `string/6.ans`。 该样例满足测试点 $19\sim21$ 的约束条件。 ### 数据范围 对于所有测试数据，均有： - $1\le n\le 2\times10^5$； - 对于所有 $i\ (1\le i\le n)$，均有 $1\le a_i\le10^9$，且 $c_i$ 为小写英文字母。 ::cute-table{tuack} | 测试点编号 | $n\le$ | $\max_{i=1}^{n}a_i\le$ | | :-: | :-: | :-: | | $1$ | $1$ | $5$ | | $2\sim4$ | $2$ | $5$ | | $5,6$ | $10$ | $1$ | | $7,8$ | $10$ | $50$ | | $9$ | $2000$ | $1$ | | $10\sim12$ | $2000$ | $50$ | | $13\sim16$ | $2000$ | $10^9$ | | $17,18$ | $2\times10^5$ | $1$ | | $19\sim21$ | $2\times10^5$ | $500$ | | $22\sim25$ | $2\times10^5$ | $10^9$ |