回文串（string）

时间限制： 1.0 s
内存限制： 1024 MiB

题目描述

小 R 有一个长度为 $L$ 的字符串 $S = s_1 \dots 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$ 改成回文串。

相邻两段中的字符可以相同。

小 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) 改成回文串。

输入格式

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

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

输出格式

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

样例 1

输入：

3
2 a
2 b
1 c

输出：

2

样例 1 解释

小 R 的字符串 (S) 由 3 段构成：

• 第 1 段由 2 个 a 组成；
• 第 2 段由 2 个 b 组成；
• 第 3 段由 1 个 c 组成。

依次拼接得到：

[ S=\texttt{aabbc} ]

小 R 可以将最后一个字符 c 和倒数第二个字符 b 都改为 a，得到回文串 aabaa，共修改 2 个位置的字符。

可以证明，小 R 最少需要修改 2 个位置的字符，才能将 (S) 改成回文串。

样例 2

输入：

2
2 a
3 a

输出：

0

样例 2 解释

小 R 的字符串 (S) 由 2 段构成：

• 第 1 段由 2 个 a 组成；
• 第 2 段由 3 个 a 组成。

依次拼接得到：

[ S=\texttt{aaaaa} ]

则 (S) 已经是回文串，不需要修改。

样例 3

输入：

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

输出：

3000000000

样例 4

见题目目录下的 string/4.in 与 string/4.ans。

该样例满足测试点 10～12 的约束条件。

样例 5

见题目目录下的 string/5.in 与 string/5.ans。

该样例满足测试点 13～16 的约束条件。

样例 6

见题目目录下的 string/6.in 与 string/6.ans。

该样例满足测试点 19～21 的约束条件。

数据范围

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

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