小 R 有一个长度为 L 的字符串 S = s_1 s_2 \cdots s_L，其中只包含小写英文字母。小 R 发现，虽然 S 可能很长，但它可以分成 n 个连续的段，其中第 i 段由 a_i 个小写英文字母 c_i 构成。把这 n 段依次拼接起来便得到 S，因此 L = \sum_{i=1}^{n} a_i。相邻两段中的字符可以相同。
小 X 喜欢回文串。若一个字符串反转后与原字符串相同，就称它是回文串，例如 \texttt{aba}、\texttt{abba} 都是回文串，而 \texttt{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 改成回文串。
3 2 a 2 b 1 c
2
2 2 a 3 a
0
6 1000000000 a 1000000000 a 1000000000 a 1000000000 b 1000000000 b 1000000000 b
3000000000
样例 1 解释：S = \texttt{aabbc}。可以把最后一个 \texttt{c} 和倒数第二个 \texttt{b} 都改成 \texttt{a}，得到回文串 \texttt{aabaa}，共改 2 个位置；可以证明不能只改 1 个，所以答案是 2。
样例 2 解释：S = \texttt{aaaaa} 已经是回文串，答案是 0。
样例 3 解释：S 是 10^9 个 \texttt{a} 接 10^9 个 \texttt{b} 再接 10^9 个 \texttt{b}。左边 3 \times 10^9 个位置全是 \texttt{a}，右边 3 \times 10^9 个位置全是 \texttt{b}，配对的 3 \times 10^9 对字符全部不同，每对至少改一个，答案 3000000000。
数据范围
• 1 \le n \le 2 \times 10^5；
• 对每个 i，1 \le a_i \le 10^9，c_i 为小写英文字母。
注意 L = \sum a_i 可以到 2 \times 10^{14}，答案也要用 \texttt{long long} 存。
测试点构成（共 25 个测试点）
| 测试点 | 规模 |
|---|---|
| 1 ~ 4 | n \le 2，L \le 7，手算即可 |
| 5 ~ 8 | n \le 10，L \le 300 |
| 9 ~ 12 | n \le 2000，\max a_i \le 50 |
| 13 ~ 16 | n \le 2000，a_i 可达 10^9（L 达到 10^{12}） |
| 17 ~ 21 | n 达到 2 \times 10^5，但 L \le 2 \times 10^8 |
| 22 ~ 25 | n 与 L 同时取到最大（2 \times 10^{14}） |
提示
只看「字符不同」的那些对称位置对：若 s_i = s_{L+1-i}，这一对不用改；若不相等，至少改一个，而且改一个就够了（把其中一个改成另一个）。所以答案 = 满足 s_i \ne s_{L+1-i} 的 i \le \lfloor L/2 \rfloor 的个数，不同位置对之间互不影响。
但 L 太大，不能把串真的造出来。注意到「从左边数第 i 个字符」和「从右边数第 i 个字符」都只能按整段变化：用两个指针分别从段首、段尾走，每次取左右剩余长度的较小值 t，这一段范围内左边全是 c_i、右边全是 c_j，于是这一整批 t 对要么全要改要么全不改，累加后把指针推进。总复杂度 O(n)。