Bring Balance
Contest: Codeforces Round 794 (Div. 1)
Difficulty rating: 2600
Tags: brute force, constructive algorithms, greedy

Alina has a bracket sequence $$$s$$$ of length $$$2n$$$, consisting of $$$n$$$ opening brackets '(' and $$$n$$$ closing brackets ')'. As she likes balance, she wants to turn this bracket sequence into a balanced bracket sequence.

In one operation, she can reverse any substring of $$$s$$$.

What's the smallest number of operations that she needs to turn $$$s$$$ into a balanced bracket sequence? It can be shown that it's always possible in at most $$$n$$$ operations.

As a reminder, a sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), and (()(())) are balanced, while )(, ((), and (()))( are not.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line of each test case contains a string $$$s$$$ of length $$$2n$$$, consisting of $$$n$$$ opening and $$$n$$$ closing brackets.

The sum of $$$n$$$ over all test cases doesn't exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, in the first line output a single integer $$$k$$$ $$$(0 \le k \le n)$$$  — the smallest number of operations required.

The $$$i$$$-th of the next $$$k$$$ lines should contain two integers $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le 2n$$$), indicating that in the $$$i$$$-th operation, Alina will reverse the substring $$$s_ls_{l+1} \ldots s_{r-1}s_r$$$. Here the numeration starts from $$$1$$$.

If there are multiple sequences of operations with the smallest length which transform the sequence into a balanced one, you can output any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the string is already balanced.

In the second test case, the string will be transformed as follows: ())((()))( $$$\to$$$ ()()(()))( $$$\to$$$ ()()(())(), where the last string is balanced.

In the third test case, the string will be transformed to ((()))((())), which is balanced.

Example input:
3
2
(())
5
())((()))(
6
())((()))(()

Example output:
0
2
3 4
9 10
1
2 11

Editorial:
Let's denote ( by $$$1$$$ and ) by $$$-1$$$. Then we need to achieve a sequence in which all prefix sums are nonnegative.
Let our sequence be $$$a_1, a_2, \ldots, a_{2n}$$$, and denote $$$pref_i = a_1 + a_2 + \ldots + a_i$$$ for each $$$0 \le i \le 2n$$$.
Key observation: It's always possible to get a balanced sequence in at most $$$2$$$ operations.
Proof: Let $$$0 \le i \le 2n$$$ be the index for which the value of $$$pref_i$$$ is the largest (if there are several such $$$i$$$, choose any). Let's reverse segments $$$a[1:i]$$$ and $$$a[i+1:2n]$$$, getting sequence $$$a_i, a_{i-1}, \ldots, a_1, a_{2n}, a_{2n-1}, \ldots, a_{i+1}$$$.
It's easy to show that this sequence is balanced. $$$a_i + a_{i-1} + \ldots + a_j = pref_i - pref_{j-1} \ge 0$$$ for any $$$j \le i$$$, and $$$a_j + a_{j-1} + \ldots + a_{i+1} = pref_j - pref_i \le 0$$$ for any $$$j \ge i$$$, so $$$a_i + a_{i-1} + \ldots + a_i + a_{2n} + \ldots + a_{j+1} = -(a_j + a_{j-1} + \ldots + a_{i+1}) \ge 0$$$ for any $$$j \ge i$$$. So, all prefix sums are nonnegative, as desired.
It remains to check if we can make our sequence balanced in less than $$$2$$$ operations.
Checking if $$$0$$$ operations are enough is trivial: just check if the initial sequence is balanced. Now, let's check if we can make the sequence (which initially isn't balanced) balanced in exactly one operation.
Let $$$l$$$ be the smallest index for which $$$pref_l < 0$$$, and $$$r$$$ be the largest such index. Suppose that we will reverse the segment $$$a[L:R]$$$. Clearly, $$$L \le l$$$, as otherwise, we would have a negative prefix sum. Similarly $$$R > r$$$. After reversing, we need to worry only about the $$$i$$$-th prefix sum for each $$$i$$$ from $$$L$$$ to $$$R-1$$$, all others will be nonnegative.
The $$$i$$$-th prefix sum for such $$$i$$$ will be equal to $$$pref_{L-1} + (pref_R - pref_{R + L - 1 - i})$$$. So, segment $$$[L, R]$$$ will be good iff $$$pref_{L-1} + pref_R \ge pref_i$$$ for all $$$L -1 \le i \le R$$$.
It's easy to show that if any such segment $$$[L, R]$$$ works, then also the segment $$$[L_1, R_1]$$$ works, where $$$L_1$$$ is the index from $$$[0, l]$$$ for which $$$pref_{L_1}$$$ is the largest, and $$$R_1$$$ is the index from $$$[r+1, 2n]$$$ for which $$$pref_{R_1}$$$ is the largest. Indeed, suppose that there is some $$$L_1 \le i \le R_1$$$ such that $$$pref_{L_1} + pref_{R_1} < pref_i$$$. If $$$i \le l$$$, then $$$pref_i < pref_{L_1}$$$, contradiction. If $$$i > r$$$, then $$$pref_i < pref_{R_1}$$$, contradiction. If $$$l < i \le r$$$, then $$$i$$$ is inside any such segment $$$[L, R]$$$, and $$$pref_i > pref_L + pref_R$$$ for any choice of $$$L, R$$$.
So, it's enough to choose segment $$$[L_1, R_1]$$$ and to check if the sequence becomes balanced after reversing it.