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

Input 1

5
((())

Output 1

6

Input 2

10
)()()(()()

Output 2

12

Template

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

# print your output