Background

Yukari Yakumo has the ability to manipulate boundaries. Ran Yakumo, as her shikigami, also has some ability to operate boundaries. However, Chen, as Ran Yakumo's shikigami, is still not skilled enough and cannot interfere with boundaries too much.

So Ran Yakumo plans to teach Chen how to use boundaries. A boundary can be abstracted as layers of parentheses, and operating a boundary is essentially modifying a parentheses sequence. Since Chen's ability is still limited, she can only perform some simple building and destroying of boundaries.

Even so, with simple operations, one boundary can be transformed into another. As practice for Chen, Ran found two boundary templates. The difficulty of transforming one boundary into the other is the minimum number of times Chen needs to use her ability. But because the boundaries are too long, Ran decides to write a program (?) to help her compute the boundary difficulty.

Problem Description

A boundary can be abstracted as a parentheses sequence consisting of round brackets. Define the following:

• Let $D_i$ be a nested parentheses sequence. Here $D_0$ is the 0-th order nested parentheses sequence, defined as a single pair of brackets $\verb!()!$; and for $k \geq 1$, $D_k$ is the $k$-th order nested parentheses sequence, defined as $\verb!(!D_{k-1}\verb!)!$, i.e. adding one layer of brackets outside $D_{k-1}$.
• Let $F_i$ be a tiled parentheses sequence. Here $F_0$ is the 0-th order tiled parentheses sequence, defined as a single pair of brackets $\verb!()!$; and for $k \geq 1$, $F_k$ is the $k$-th order tiled parentheses sequence, defined as $\verb!()!F_{k-1}$, i.e. adding one pair of brackets to the left of $F_{k-1}$.

For example, $\verb!((()))!$ is $D_2$, and $\verb!()()()()!$ is $F_{3}$.

Now Ran gives two valid parentheses sequences $A$ and $B$, both of length $n$. Chen can transform sequence $A$ using the following operations:

• Choose any non-negative integer $k$, choose a substring of the parentheses sequence that is a $k$-th order nested parentheses sequence, and then change it into a $k$-th order tiled parentheses sequence.
• Choose any non-negative integer $k$, choose a substring of the parentheses sequence that is a $k$-th order tiled parentheses sequence, and then change it into a $k$-th order nested parentheses sequence.

The definitions of "valid parentheses sequence" and "substring" are given in the Hint section.

Now you need to find the minimum number of operations required to transform sequence $A$ into sequence $B$. It can be proven that there is always an operation plan that can transform $A$ into $B$.

Input Format

• The first line contains one integer $n$, representing the length of the parentheses sequences $A$ and $B$.
• The next line contains $n$ characters describing parentheses sequence $A$. It is guaranteed that sequence $A$ is valid.
• The next line contains $n$ characters describing parentheses sequence $B$. It is guaranteed that sequence $B$ is valid.

Output Format

• One line containing one integer, representing the minimum number of steps needed to convert $A$ into $B$ (it may be $0$, meaning no operation is performed).

14
((()())(()()))
()()()()()()()

6

14
((()())(()()))
(()())(()())()

10

Hint

Sample $3$ is in the attached file $\textbf{\textit{border3.in/border3.ans}}$.
Sample $4$ is in the attached file $\textbf{\textit{border4.in/border4.ans}}$. It satisfies special property $\text{A}$ (see below).
Sample $5$ is in the attached file $\textbf{\textit{border5.in/border5.ans}}$.

Explanation for Sample 1

• Step 1: $\texttt{((\underline{()()})(()()))}\to\texttt{((\underline{(())})(()()))}$.
• Step 2: $\texttt{(((()))(\underline{()()}))}\to\texttt{(((()))(\underline{(())}))}$.
• Step 3: $\texttt{(((()))\underline{((()))})}\to\texttt{(((()))\underline{()()()})}$.
• Step 4: $\texttt{(\underline{((()))}()()())}\to\texttt{(\underline{()()()}()()())}$.
• Step 5: $\texttt{(\underline{()()()()()()})}\to\texttt{(\underline{(((((())))))})}$.
• Step 6: $\texttt{\underline{((((((()))))))}}\to\texttt{\underline{()()()()()()()}}$.

It can be proven that there is no shorter plan.

Hint

A valid parentheses sequence is defined in the following form:

• $\verb!()!$ is a valid parentheses sequence.
• If $A$ is a valid parentheses sequence, then $\verb!(!A\verb!)!$ is a valid parentheses sequence.
• If both $A$ and $B$ are valid parentheses sequences, then $AB$ is a valid parentheses sequence.

We say $A$ is a substring of $B$ if and only if we delete some characters at the beginning of $B$ (possibly deleting none), and then delete some characters at the end of $B$ (possibly deleting none), and the remaining character sequence is exactly the same as $A$.

Constraints and Notes

This problem has $20$ test points, with $5$ points per test point. The final score is the sum of the scores of all test points.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \bm{n\le } & \textbf{Special property} \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}$$

Special property $\textbf{A}$: it is guaranteed that $B$ is a $(n\div 2-1)$-th order tiled parentheses sequence.

Friendly Reminder

Considering that contestants may read strings in different ways, it is guaranteed that the input file has no extra spaces at the end of each line, and each line ends with \n (that is, there will be no extra \r).

Translated by ChatGPT 5