BALANCED PARENTHESES

A string consisting of parentheses is considered "balanced" if (a) all opening parentheses have corresponding closing parentheses, and (b) no closing parentheses occur without a preceding opening parenthesis. For example:

• The string (()) is balanced.
• The string ()() is also balanced.
• The string (() is not balanced because the first opening parenthesis never closes.
• The string ())( is not balanced because the second closing parenthesis has no preceding opening parenthesis.
• The string (()())() is balanced.

Given a string S consisting of N characters, each of which is either '(' or ')', the string S is not necessarily balanced. Count how many substrings (i.e., "pieces" of S) are balanced.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that, after reading the string S, prints the number of balanced sub-strings of it.

Input Files:

The input files with the name cntbal.in are text files with the following structure: The first line contains an integer N (where 1 ~\le~ N ~\le~ 1.000.000), the number of characters in the string. The next line contains the N characters forming the string S. Assume that the string consists only of characters '(' or ')'.

Output Files:

The output files with the name cntbal.out are text files consisting of a single line with a single integer: the number of balanced sub-strings of S.

Examples of Input - Output Files:

The balanced substrings are highlighted.

1o

STDIN (cntbal.in)

5
())()

STDOUT (cntbal.out)

2

Explanation

())()
-- 
   --

2o

STDIN (cntbal.in)

8
(()(()))

STDOUT (cntbal.out)

5

Explanation

(()(()))
 -- 
    --
   ----
 ------
--------

3o

STDIN (cntbal.in)

3
))(

STDOUT (stdbal.out)

0

Explanation

There is no balanced substring.

4o

STDIN (cntbal.in)

6
()()()

STDOUT (cntbal.out)

6

Explanation

()()()
--
  --
    --
----
  ----
------

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: longsumk *)

for PASCAL coders

/* USER: username
LANG: C
TASK: cntbal */

for C coders

/* USER: username
LANG: C++
TASK: cntbal */

for C++ coders

/* USER: username
LANG: Java
TASK: cntbal */

for Java coders

# USER: username
# LANG: Python
# TASK: cntbal

for Python coders