B. Весь мир — задача по программированию (усложнённая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это усложнённая версия задачи. В этой версии $$$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$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 300\,000$$$) — длина строки, которую подарили Васе.

Вторая строка содержит одну строку, состоящую ровно из $$$n$$$ символов, каждый из которых — либо открывающая скобка «(», либо закрывающая скобка «)».

Выходные данные

В первой строке выведите одно целое число — максимальную красоту строки, которую можно получить, поменяв местами какие-то два символа.

Во второй строке выведите целые числа $$$l$$$ и $$$r$$$ ($$$1 \leq l, r \leq n$$$) — номера символов, которые нужно поменять местами, чтобы максимизировать красоту строки.

Если возможных замен несколько, выведите любую из них.

Примеры
Входные данные
10
()()())(()
Выходные данные
5
8 7
Входные данные
12
)(()(()())()
Выходные данные
4
5 10
Входные данные
6
)))(()
Выходные данные
0
1 1
Примечание

В первом примере после обмена местами $$$7$$$-й и $$$8$$$-й скобок получается строка «()()()()()», её циклические сдвиги на $$$0, 2, 4, 6, 8$$$ являются правильными скобочными последовательностями.

Во втором примере после обмена местами $$$5$$$-й и $$$10$$$-й скобок получается строка «)(())()()(()», её циклические сдвиги на $$$11, 7, 5, 3$$$ являются правильными скобочными последовательностями.

В третьем примере какие бы две скобки мы не поменяли местами, число циклических сдвигов, являющихся правильными скобочными последовательностями, будет равно $$$0$$$.