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