Это усложнённая версия задачи. В этой версии \(n \le 300\,000\).
Вася — опытный составитель задач для олимпиад по программированию. Как и все великие творцы, Вася столкнулся с творческим кризисом. Чтобы исправить ситуацию, Петя подарил ему строку, состоящую только из открывающих и закрывающих скобок. Петя считает, что красотой строки из скобок называется количество её циклических сдвигов, которые приводят к правильной скобочной последовательности.
Чтобы отвлечься от проблем, Вася хочет выбрать любые две позиции в строке (не обязательно различных) и поменять местами символы на этих позициях. Такую операция Вася проделает ровно один раз. Ему стало интересно, какой максимальной красоты строки можно добиться, применив данную операцию. Помогите ему.
Напомним, что последовательность \(s\) из круглых скобок называется правильной, если верно одно из:
- \(s\) является пустой;
- \(s\) равна «(\(t\))», где \(t\) — правильная скобочная последовательность;
- \(s\) равна \(t_1 t_2\), то есть конкатенации \(t_1\) и \(t_2\), где \(t_1\) и \(t_2\) являются правильными скобочными последовательностями.
Например, последовательности «(()())», «()» являются правильными, а «)(» и «())» нет.
Циклическим сдвигом строки \(s\) длины \(n\) на \(k\) (\(0 \leq k < n\)) называется строка, представляющая собой конкатенацию (сложение) последних \(k\) символов строки \(s\) и первых \(n - k\) символов строки \(s\). Например, циклический сдвиг строки «(())()» на \(2\) равен «()(())».
Циклические сдвиги на \(i\) и \(j\) называются различными, если \(i \ne j\).
Выходные данные
В первой строке выведите одно целое число — максимальную красоту строки, которую можно получить, поменяв местами какие-то два символа.
Во второй строке выведите целые числа \(l\) и \(r\) (\(1 \leq l, r \leq n\)) — номера символов, которые нужно поменять местами, чтобы максимизировать красоту строки.
Если возможных замен несколько, выведите любую из них.
Примечание
В первом примере после обмена местами \(7\)-й и \(8\)-й скобок получается строка «()()()()()», её циклические сдвиги на \(0, 2, 4, 6, 8\) являются правильными скобочными последовательностями.
Во втором примере после обмена местами \(5\)-й и \(10\)-й скобок получается строка «)(())()()(()», её циклические сдвиги на \(11, 7, 5, 3\) являются правильными скобочными последовательностями.
В третьем примере какие бы две скобки мы не поменяли местами, число циклических сдвигов, являющихся правильными скобочными последовательностями, будет равно \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
()()())(()
|
5
8 7
|
|
2
|
12
)(()(()())()
|
4
5 10
|
|
3
|
6
)))(()
|
0
1 1
|