Swapping Brackets

Task

Do you remember Baby Bob? His older brother, Balanced Benjamin would like to give a gift to his brother. He has a string $S$ of length $N$, where $N$ is even. The string consists of $\frac{N}{2}$ opening brackets ( and $\frac{N}{2}$ closing brackets ).

As Bob likes valid bracket sequences, Benjamin would like to turn $S$ into a valid bracket sequence by swapping (not necessarily adjacent) characters in $S$.

A bracket sequence is valid if 1 and + characters can be inserted into it so that it becomes a valid mathematical expression. For example, ()(()(())) is a valid bracket sequence.

Since he's less mathematically inclined than his younger brother, he asks for your help.

Write a program that turns $S$ into a balanced bracket sequence by swapping characters in $S$ using the minimum number of swaps.
If there are more than one way to do this, you can output any of them.

Input data

The input file consists of:

• a line containing integer $N$, the length of $S$.
• a line containing string $S$, a bracket sequence of length $N$.

Output data

The output file consists of:

• a line containing integer $R$, the minimum number of swaps necessary.
• $R$ lines, each line contains the indices ($0$-based) of the two characters to be swapped.

Constraints and clarifications

• $1 \leq N \leq 10^6$.
• $N$ is even.
• $S$ has length $N$ and only contains characters ( and ).

Example 1

stdin

4
)()(

stdout

1
0 3

Explanation

In the first sample case the string after the swap looks like this: (()).

Example 2

stdin

8
)))((()(

stdout

2
0 5
7 1

Explanation

In the second sample case the swaps change string $S$ the following way:
)))((()( $\rightarrow$ ())(())( $\rightarrow$ (()(()))

Example 3

stdin

10
()(()(()))

stdout

0

Explanation

In the third sample case the bracket sequence is already valid.