CF1239B.The World Is Just a Programming Task (Hard Version)

This is a harder version of the problem. In this version, $n \le 300\,000$.

Vasya is an experienced developer of programming competitions' problems. As all great minds at some time, Vasya faced a creative crisis. To improve the situation, Petya gifted him a string consisting of opening and closing brackets only. Petya believes, that the beauty of the bracket string is a number of its cyclical shifts, which form a correct bracket sequence.

To digress from his problems, Vasya decided to select two positions of the string (not necessarily distinct) and swap characters located at this positions with each other. Vasya will apply this operation exactly once. He is curious what is the maximum possible beauty he can achieve this way. Please help him.

We remind that bracket sequence $s$ is called correct if:

• $s$ is empty;
• $s$ is equal to "($t$)", where $t$ is correct bracket sequence;
• $s$ is equal to $t_1 t_2$, i.e. concatenation of $t_1$ and $t_2$, where $t_1$ and $t_2$ are correct bracket sequences.

For example, "(()())", "()" are correct, while ")(" and "())" are not.

The cyclical shift of the string $s$ of length $n$ by $k$ ($0 \leq k \lt n$) is a string formed by a concatenation of the last $k$ symbols of the string $s$ with the first $n - k$ symbols of string $s$. For example, the cyclical shift of string "(())()" by $2$ equals "()(())".

Cyclical shifts $i$ and $j$ are considered different, if $i \ne j$.

这是该问题的一个更难版本。在此版本中，$n \le 300\,000$。

瓦夏是一位经验丰富的编程竞赛题目开发者。如同所有伟大思想者一样，瓦夏也曾遭遇过创作危机。为改善这一状况，佩佳送给他一个仅由左括号和右括号组成的字符串。佩佳认为，该括号串的“美感”等于其循环移位中能构成合法括号序列的个数。

为了暂时摆脱困扰，瓦夏决定选取字符串中的两个位置（二者可以相同），并交换这两个位置上的字符。瓦夏将恰好执行一次该操作。他很好奇：通过这种方式，所能达到的最大美感值是多少？请帮助他。

我们回顾：括号序列 $s$ 被称为合法的，当且仅当满足以下条件之一：

• $s$ 为空；
• $s$ 形如 "($t$)"，其中 $t$ 是合法括号序列；
• $s$ 形如 $t_1 t_2$，即 $t_1$ 与 $t_2$ 的拼接，其中 $t_1$ 和 $t_2$ 均为合法括号序列。

例如，"(()())"、"()" 是合法的，而 ")(" 和 "())" 则不合法。

长度为 $n$ 的字符串 $s$ 关于 $k$（其中 $0 \leq k \lt n$）的循环移位，是指将 $s$ 的最后 $k$ 个字符与前 $n - k$ 个字符拼接所形成的字符串。例如，字符串 "(())()" 关于 $2$ 的循环移位结果为 "()(())"。

若 $i \ne j$，则循环移位 $i$ 与 $j$ 被视为不同的移位。

The first line contains an integer $n$ ($1 \le n \le 300\,000$), the length of the string.

The second line contains a string, consisting of exactly $n$ characters, where each of the characters is either "(" or ")".

第一行包含一个整数 $n$（$1 \le n \le 300\,000$），表示字符串的长度。

第二行包含一个恰好由 $n$ 个字符组成的字符串，其中每个字符均为 ( 或 )。

The first line should contain a single integer — the largest beauty of the string, which can be achieved by swapping some two characters.

The second line should contain integers $l$ and $r$ ($1 \leq l, r \leq n$) — the indices of two characters, which should be swapped in order to maximize the string's beauty.

In case there are several possible swaps, print any of them.

第一行应包含一个整数——通过交换某两个字符所能达到的最大字符串美观度。

第二行应包含两个整数 $l$ 和 $r$（$1 \leq l, r \leq n$）——为使字符串美观度最大，需交换的两个字符的下标。

若存在多种可能的交换方式，请输出任意一种。

In the first example, we can swap $7$-th and $8$-th character, obtaining a string "()()()()()". The cyclical shifts by $0, 2, 4, 6, 8$ of this string form a correct bracket sequence.

In the second example, after swapping $5$-th and $10$-th character, we obtain a string ")(())()()(()". The cyclical shifts by $11, 7, 5, 3$ of this string form a correct bracket sequence.

In the third example, swap of any two brackets results in $0$ cyclical shifts being correct bracket sequences.

在第一个例子中，我们可以交换第 $7$ 个和第 $8$ 个字符，得到字符串 "()()()()()"。该字符串的循环移位（移位量分别为 $0, 2, 4, 6, 8$）均构成合法括号序列。

在第二个例子中，交换第 $5$ 个和第 $10$ 个字符后，我们得到字符串 ")(())()()(()"。该字符串的循环移位（移位量分别为 $11, 7, 5, 3$）构成合法括号序列。

在第三个例子中，任意交换两个括号，均导致 $0$ 个循环移位构成合法括号序列。