「Wdoi-5」建立与摧毁的结界

境界可以被抽象为由圆括号组成的括号序列。现做出如下定义： - 定义 $D_i$ 为**嵌套括号序列**。其中 $D_0$ 为零阶嵌套括号序列，被定义为单组括号 $\verb!()!$；而 $D_k$ 则为 $k$ 阶嵌套括号序列（$k \geq 1$）定义为 $\verb!(!D_{k-1}\verb!)!$，即在 $D_{k-1}$ 的外层增添了一层括号。 - 定义 $F_i$ 为**平铺括号序列**。其中 $F_0$ 为零阶平铺括号序列，被定义为单组括号 $\verb!()!$；而 $F_k$ 则为 $k$ 阶平铺括号序列（$k \geq 1$），定义为 $\verb!()!F_{k-1}$，即在 $F_{k-1}$ 的左侧增添了一对括号。 例如，$\verb!((()))!$ 为 $D_2$，$\verb!()()()()!$ 为 $F_{3}$。 现在蓝给出了两个长度为 $n$ 的**合法**括号序列 $A$ 和 $B$。橙可以用以下操作对序列 $A$ 进行变换： - 选择任意非负整数 $k$，选择括号序列的一个子串满足其为一个 $k$ 阶嵌套括号序列，然后将其变为 $k$ 阶平铺括号序列。 - 选择任意非负整数 $k$，选择括号序列的一个子串满足其为一个 $k$ 阶平铺括号序列，然后将其变为 $k$ 阶嵌套括号序列。 **提示说明**处有「合法括号序列」与「子串」的定义。 现在需要求出将序列 $A$ 变换为序列 $B$ 所需的最少操作数。可以证明，总存在一种操作方案能将序列 $A$ 变换为序列 $B$。 ## Input - 第一行共有一个整数 $n$，表示 $A$ 与 $B$ 括号序列的长度。 - 接下来一行，共有 $n$ 个字符，描述括号序列 $A$。保证序列 $A$ 合法。 - 接下来一行，共有 $n$ 个字符，描述括号序列 $B$。保证序列 $B$ 合法。 ## Output - 共一行，一个整数，表示将 $A$ 转换为 $B$ 需要的最少步数（可能为 $0$，也就是不进行任何操作）。 [samples] ## Background 八云紫拥有操控境界程度的能力。作为其式神的八云蓝，同样拥有一定程度的操作境界的能力，而作为八云蓝的式神橙，却因为功力尚且不足，而无法对境界进行过多的干预了。 于是八云蓝打算教教橙，境界的用法。境界可以被抽象成一层一层的括号，操作境界本质上就是对括号序列进行修改。由于橙的能力尚且不足，因此只能进行一些简单的境界的建立与摧毁。 尽管如此，通过简单的操作，亦可以把一个境界转换为另外一个境界。为了给橙作为练习，蓝找来了两个境界的范本。将其中一个境界转换为另外一个境界的难度，就是橙需要施用能力的最小次数。但是由于境界实在太长，蓝决定写一个程序（？）来帮帮她计算出境界的难度。 ## Note 样例 $3$ 见下发的附件 $\textbf{\textit{border3.in/border3.ans}}$。 样例 $4$ 见下发的附件 $\textbf{\textit{border4.in/border4.ans}}$。满足特殊性质 $\text{A}$（见下文）。 样例 $5$ 见下发的附件 $\textbf{\textit{border5.in/border5.ans}}$。 #### 样例 1 解释 - 第一步：$\texttt{((\underline{()()})(()()))}\to\texttt{((\underline{(())})(()()))}$。 - 第二步：$\texttt{(((()))(\underline{()()}))}\to\texttt{(((()))(\underline{(())}))}$。 - 第三步：$\texttt{(((()))\underline{((()))})}\to\texttt{(((()))\underline{()()()})}$。 - 第四步：$\texttt{(\underline{((()))}()()())}\to\texttt{(\underline{()()()}()()())}$。 - 第五步：$\texttt{(\underline{()()()()()()})}\to\texttt{(\underline{(((((())))))})}$。 - 第六步：$\texttt{\underline{((((((()))))))}}\to\texttt{\underline{()()()()()()()}}$。 可以证明，不存在更短的方案。 #### 提示 **合法括号序列**通过这样一个形式定义： - $\verb!()!$ 是合法括号序列。 - 若 $A$ 是合法括号序列，那么 $\verb!(!A\verb!)!$ 是合法括号序列。 - 若 $A,B$ 均为合法括号序列，那么 $AB$ 是合法括号序列。 我们称 $A$ 是 $B$ 的**子串**，当且仅当删除 $B$ 开头若干个字符（可以不删除），再删除 $B$ 末尾若干个字符（可以不删除），剩下来的字符序列与 $A$ 完全相同。 #### 数据范围及约定 本题共有 $20$ 个测试点，每个测试点 $5$ 分。最终分数为所有测试点分数之和。 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \bm{n\le } & \textbf{特殊性质} \cr\hline 1\sim 4 & 10 & - \cr\hline 5\sim 7 & 2\times 10^3 & \text{A} \cr\hline 8\sim 10 & 2\times 10^3 & - \cr\hline 11\sim 15 & 10^6 & \text{A} \cr\hline 16\sim 20 & 10^6 & - \cr\hline \end{array} $$ **特殊性质** $\textbf{A}$：保证 $B$ 是 $(n\div 2-1)$ 阶平铺括号序列。 #### 友情提醒 考虑到选手可能会用不同的方式进行字符串的读入，这里保证输入文件**每行末尾没有多余空格**，并且每行都以 `\n` 结尾（也就是说，不会出现多余的 `\r`）。