题目描述

这是一道字符串题。

相信大家都有听说过括号序列。

在本题，括号序列指的是只由 $(，)$组成的字符串。

一个好的括号序列归纳定义如下：

归纳基：() 是一个好的括号序列

归纳步：若 $A,B$ 都是好的括号序列，那么 (A) 和 AB 都是好的括号序列。

例如，(()())() 是一个好的括号序列；)(()()() 是括号序列，但不是一个好的括号序列；(aasdfa(Asd)) 不是一个括号序列。

现在你有一个括号序列 $s$ 。

求有多少个子串是好的括号序列。

输入描述

第一行一个正整数 $n$ 表示序列长度。

第二行一个长度为 $n$ 的括号序列表示 $s$。

输出描述

一个正整数

输入样例

7
(()()((

输出样例

3

数据范围

对于 $100\%$ 的数据，满足 $n\leq 10^6$