How Do You Make a Problem?

Limits 2s, 1.0 GB

I am very busy these days. So when I was told, I have to create a problem for the contest, I was slightly annoyed. But regardless I made this problem. And this is the story of how I did so.

To create a problem, you first need a setting or scenario. There are lots of well-known settings in competitive programming, Array of numbers, grid of numbers, strings, permutations, graphs and so on. After a bit of pondering, I decided to start with a balanced string of brackets. A sequence of brackets is balanced if you can turn it into a valid arithmetic expression by adding characters ‘1’ and ‘+’. For example `(())(()())` is a balanced bracket string. But `((()`, `())()`, `)(` are not. So we start with the following setting, You will be given a string of length nn of brackets that is balanced.

Now there needs to be a task, that you will do. The task could be to find some construction or check some conditions. It could also be an optimization where you have to find the minimum value or some maximum value. Now, these are generally a bit hard to work with. So I chose the following task, you have to count something. But count what? There are lots of things to count in a balanced bracket sequence. The answer was in front of me always, count balanced substrings! i.e. you have to count the number of substrings of the input string that are also balanced. A substring of a string is part of the string obtained by deleting a prefix (possibly empty) and deleting a suffix (possibly empty). For example in `(()(()())`, `(()` is a substring (that occurs twice). So you have to count the number of balanced substrings of the input string.

But the problem felt too easy. So I decided to make it hard. How do you make a problem hard? Add queries to it of course! So instead of counting balanced substrings of the original string, you will be given qq queries. Each query is a range ll rr of the original string. And for each query, you have to count the number of balanced substring of the substring built by taking indices ll, …, rr . (1-indexed)

Now I am happy, so chop chop, solve the problem!

Input

The first line of input will contain a positive integer nn, the length of the input string of brackets. Second line will contain a balanced string ss of `(` and `)`.

Third line will contain a positive integer qq, the number of queries. Next qq lines each contain a query as two positive integer ll and rr separated by space. Meaning that you have to count the number of balanced substrings of s[l.r]s[l….r]

2n2×1062 \leq n \leq 2\times 10^6

1q1061 \leq q \leq 10^6

1lrn1 \leq l \leq r \leq n

Output

For each query, output the answer in a separate line.

Sample

InputOutput
10
(())(()())
4
5 10
1 5
4 5
1 10
4
2
0
7