这是问题的更难版本。在此版本中,$$$n \le 300\,000$$$。
Vasya 是一位经验丰富的编程竞赛问题开发人员。和所有伟大的思想家一样,瓦夏也曾面临过创造性危机。为了改善这种情况,Petya 送给他一根仅由左括号和右括号组成的字符串。 Petya 认为,括号串的美妙之处在于它的许多循环移位,它们形成了正确的括号序列。
为了偏离他的问题,Vasya 决定选择字符串的两个位置(不一定是不同的)并将位于该位置的字符彼此交换。 Vasya 将仅应用此操作一次。他很好奇通过这种方式他能达到的最大可能的美感是多少。请帮助他。
我们提醒一下,如果满足以下条件,括号序列 $$$s$$$ 被称为正确的:
- $$$s$$$ 为空;
- $$$s$$$ 等于 "($$$t$$$)",其中 $$$t$$$ 是正确的括号序列;
- $$$s$$$ 等于 $$$t_1 t_2$$$,即 $$$t_1$$$ 和 $$$t_2$$$ 的串联,其中 $$$t_1$$$ 和 $$$t_2$$$ 是正确的括号序列。
例如,“(()())”、“()”是正确的,而“)(”和“())”则不正确。
长度为 $$$n$$$ 的字符串 $$$s$$$ 循环移位 $$$k$$$ ($$$0 \leq k < n$$$) 是由字符串 $$$s$$$ 的最后 $$$k$$$ 符号与字符串 $$$s$$$ 的前 $$$n - k$$$ 符号串联而成的字符串。例如,字符串“(())()”循环移位$$$2$$$等于“()(())”。
如果 $$$i \ne j$$$ 则循环移位 $$$i$$$ 和 $$$j$$$ 被视为不同。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300\,000$$$),即字符串的长度。
第二行包含一个字符串,由 $$$n$$$ 个字符组成,其中每个字符都是“(”或“)”。
输出
第一行应该包含一个整数——字符串的最大优点,这可以通过交换两个字符来实现。
第二行应包含整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l, r \leq n$$$) — 两个字符的索引,应交换它们以最大化字符串的美观。
如果有多个可能的交换,请打印其中任何一个。
示例
输入 #1
10 ()()())(()
输出 #1
5 8 7
输入 #2
12 )(()(()())()
输出 #2
4 5 10
输入 #3
6 )))(()
输出 #3
0 1 1
注意
在第一个示例中,我们可以交换第 $$$7$$$ 和第 $$$8$$$ 个字符,获得字符串“()()()()()”。该字符串循环移位 $$$0, 2, 4, 6, 8$$$ 形成正确的括号序列。
在第二个例子中,交换第 $$$5$$$ 和第 $$$10$$$ 个字符后,我们得到一个字符串 ")(())()()(()"。该字符串循环移位 $$$11, 7, 5, 3$$$ 形成正确的括号序列。
在第三个示例中,任意两个括号的交换都会导致 $$$0$$$ 循环移位成为正确的括号序列。