Permuted Balanced Bracket Sequence
You are given a bracket sequence of length N and Q queries. In each query, you are given two integers L and R. For each query you have to take the substring from L to R as a string S and answer the following questions:
**1.**What is the length of longest substring of S which can be permuted among themselves to get a balanced bracket sequence?
2. How many ways you can choose such longest length?
A sequence is defined as balanced bracket sequence by the following rules:
- An empty sequence is balanced.
- A sequence of the form (A) is balanced if A is balanced.
- A sequence of the form AB is balanced if A and B both are balanced.
Input
Input starts with an integer N (1<=N<=100000), denoting the length of bracket sequence.
Next line contains bracket sequence consists of ‘(’ and ‘)’ only.
Next line contain an integer Q (1<=Q<=100000), denoting total number of queries.
Following Q lines contain two integers L and R, where L<=R and 0<=L, R<=N-1.
Output
For each query answer above two questions. If you cannot form any such balanced bracket sequence print -1 instead. Follow sample output format for more clarity.
Sample
| Input | Output |
|---|---|
7 (()(()) 3 0 1 0 2 1 5 | -1 2 1 4 1 |
In above sample,
Case 1: we cannot permute any substring of “((“to get a valid balance bracket sequence.
Case 2: we can get substring of length 2 “()” starting from index 1.
Case 3: We can get 1 substrings of length 4 “)(()” starting at index 2.
