B 回文串（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$。相邻两段中的字符可以相同。

若一个字符串反转后与原字符串相同，就称它是回文串，例如 aba、abba 都是回文串，而 aabbc 不是。也就是说，字符串 $S$ 是回文串，当且仅当对于所有 $i$（$1\le i\le L$），均有 $s_i=s_{L+1-i}$。

小 X 想让小 R 把 $S$ 改成回文串。小 R 可以将 $S$ 中任意一个位置的字符修改成任意小写英文字母。他想用尽量少的修改满足小 X 的要求。

你需要帮助小 R 求出，他最少需要修改多少个位置的字符，才能将 $S$ 改成回文串。

输入格式

输入的第一行包含一个正整数 $n$。

输入的第 $i+1$（$1\le i\le n$）行包含一个正整数 $a_i$ 和一个小写英文字母 $c_i$。

输出格式

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

样例

输入样例 1

3
2 a
2 b
1 c

输出样例 1

2

输入样例 2

2
2 a
3 a

输出样例 2

0

输入样例 3

6
1000000000 a
1000000000 a
1000000000 a
1000000000 b
1000000000 b
1000000000 b

输出样例 3

3000000000

样例解释

样例 1：$S$ 由 3 段构成，拼接得到 $S=\texttt{aabbc}$。把最后一个字符 $\texttt{c}$ 和倒数第二个字符 $\texttt{b}$ 都改成 $\texttt{a}$，得到 $\texttt{aabaa}$，共修改 2 个位置，可以证明这是最少的。

样例 2：$S=\texttt{aaaaa}$ 本身已是回文串，不需要修改。

数据范围

对于所有测试数据，均有：

• $1\le n\le 2\times 10^5$；
• 对于所有 $i$，$1\le a_i\le 10^9$，且 $c_i$ 为小写英文字母。

测试点编号	$n\le$	$\max a_i\le$
$1$		$5$
$2\sim 4$	$2$
$5,6$	$10$	$1$
$7,8$		$50$
$9$	$2000$	$1$
$10\sim 12$		$50$
$13\sim 16$		$10^9$
$17,18$	$2\times 10^5$	$1$
$19\sim 21$		$500$
$22\sim 25$		$10^9$

注意：答案可能超过 $32$ 位整数范围。

---

题目来源：CSP-J 2026 第二轮（CCF CSP-J 入门级）。 题面据洛谷 P17828 整理；本平台测试数据由官方标程生成，覆盖题面「测试点编号」表里的各档子任务。