У Алины есть скобочная последовательность \(s\) длины \(2n\), состоящая из \(n\) открывающих скобок '(' и \(n\) закрывающих скобок ')'. Поскольку ей нравится баланс, она хочет превратить эту последовательность скобок в сбалансированную скобочную последовательность.
За одну операцию она может развернуть любую подстроку \(s\).
Какое наименьшее количество операций ей потребуется, чтобы превратить \(s\) в сбалансированную скобочную последовательность? Можно показать, что это всегда можно сделать за не более чем \(n\) операций.
Напомним, что скобочная последовательность называется сбалансированной, если ее можно превратить в правильное математическое выражение, добавив символы + и 1. Например, последовательности (())(), () и (()(())) являются сбалансированными, а )(, (() и (())( — нет.
Выходные данные
Для каждого набора входных данных в первой строке выведите одно целое число \(k\) \((0 \le k \le n)\) — наименьшее количество необходимых операций.
В \(i\)-й из следующих \(k\) строк должны содержаться два целых числа \(l_i, r_i\) (\(1 \le l_i \le r_i \le 2n\)), указывающие на то, что в \(i\)-й операции Алина развернет подстроку \(s_ls_{l+1} \ldots s_{r-1}s_r\). Здесь нумерация начинается с \(1\).
Если существует несколько последовательностей операций с наименьшей длиной, которые преобразуют последовательность в сбалансированную, вы можете вывести любую из них.
Примечание
В первом наборе входных данных строка уже сбалансирована.
Во втором наборе входных данных строка будет преобразована следующим образом: ())(()))( \(\to\) ()()()())( \(\to\) ()()()()(), где последняя строка сбалансирована.
В третьем наборе входных данных строка будет преобразована в ((()))((())), которая является сбалансированой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
(())
5
())((()))(
6
())((()))(()
|
0
2
3 4
9 10
1
2 11
|