[AdditionalFile2281.zip](file://AdditionalFile2281.zip?type=additional_file)

#2281. 「POI2012 R1」字母 Letters

标签: 传统 | 时间限制: 1500 ms | 内存限制: 128 MiB |

题目描述

译自 POI 2012 Stage 1. 「Letters」

给定两个长度相同且由大写英文字母组成的字符串 A 和 B，保证 A 和 B 中每种字母出现的次数相同。

每次可以交换 A 中相邻两个字符，求最少需要交换多少次可以使得 A 变成 B。

输入格式

第一行一个正整数 $n (2 \le n \le 1\ 000\ 000)$，表示字符串的长度。

第二行和第三行各一个长度为 $n$ 的字符串，并且只包含大写英文字母。

输出格式

一个非负整数，表示最少的交换次数。

样例

输入

3
ABC
BCA

输出

2

数据范围与提示

对于 $30\%$ 的数据保证 $n \le 1000$.

对于所有数据保证 $2 \le n \le 1\ 000\ 000$.

Task author: Marian M. Kedzierski.