CF2190B1 Sub-RBS (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, you only need to evaluate for whole string $ s $ , $ s $ is regular, and the constraints on $ n $ are higher. We say that a bracket sequence $ a $ is better than a bracket sequence $ b $ if one of the following holds: - $ b $ is a prefix of $ a $ , but $ a \ne b $ ; or - let $ i $ be the first position (if it exists) where $ a_i \neq b_i $ , then $ \color{red}{a_i = \texttt{(}} $ and $ \color{red}{b_i = \texttt{)}} $ . You are given a regular bracket sequence $ ^{\text{∗}} $ $ s $ of even length $ n $ . Among all non-empty subsequences $ ^{\text{†}} $ $ t $ of $ s $ that are regular bracket sequences, find the maximum possible length of $ t $ such that $ t $ is better than $ s $ . If no such $ t $ exists, report it. $ ^{\text{∗}} $ A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting the characters $ \texttt{1} $ and $ \texttt{+} $ between the original characters of the sequence. For example: - bracket sequences $ \texttt{()()} $ and $ \texttt{(())} $ are regular (the resulting expressions are $ \texttt{(1)+(1)} $ and $ \texttt{((1+1)+1)} $ ); - bracket sequences $ \texttt{)(} $ , $ \texttt{(} $ , and $ \texttt{)} $ are not. $ ^{\text{†}} $ A sequence $ a $ is a subsequence of a sequence $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) element from arbitrary positions.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ , $ n $ is even) — the length of the string $ s $ . The second line of each test case contains a sequence $ s $ of length $ n $ consisting only of characters $ \texttt{(} $ and $ \texttt{)} $ . It is guaranteed that the given sequence $ s $ is a regular bracket sequence. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, print a single integer — the maximum possible length of a non-empty subsequence $ t $ of $ s $ that is a regular bracket sequence and is better than $ s $ . If no such $ t $ exists, print $ -1 $ .

In the first example, the only non-empty regular bracket subsequence of $ s $ is $ t = s = \texttt{()} $ . Since $ t $ is not better than $ s $ , we output $ -1 $ . In the second example, we can choose $ t = \texttt{((()))} $ . The first index where $ t $ and $ s $ differ is $ i = 3 $ . Since $ t_3 = \texttt{(} $ and $ s_3 = \texttt{)} $ , $ t $ is better than $ s $ . We cannot choose a longer subsequence because the only longer regular bracket subsequence is $ s $ itself, which is not better than $ s $ . Thus, we output $ 6 $ .