← 返回题目列表

Codeforces · 1239/B

B. 世界只是一个编程任务(困难版)

中文机器翻译题面 查看原题

这是问题的更难版本。在此版本中,$$$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$$$ 循环移位成为正确的括号序列。