Bracket Sequences

Problem Statement

Give a string $s$ of length $n$ consisting of only characters ( and ). Output the number of sub-sequences of $s$ which are equal to ().

This problem can be solved without divide and conquer, but for the purpose of this exercise, please use divide and conquer.

NOTE: A subsequence of $s$ is formed by deleting some characters from $s$.

Input Format

Your first line will contain a single integer $n$. Your next line will contain $s$.

Output Format

Output the number of bracket sequences equal to () in $s$.

Constraints

• $1 \leq n \leq 10^5$

Sample Cases

5
((())

6

10
)()()(()()

12

Template

n = int(input())
s = input()

# print your output