Background

定义合法括号序列如下：

• 空串是合法括号序列。
• 若 A 是合法括号序列，则 (A) 是合法括号序列。
• 若 A 与 B 均是合法括号序列，则 AB 是合法括号序列。

Description

香穗要过生日了，所以铃音打算为香穗准备生日礼物。

铃音知道香穗喜欢玩括号序列，所以铃音打算为香穗送一个美妙的合法括号序列。

现在铃音手上有一个仅由 ( 与 ) 组成的括号序列 $S$，铃音将要选择 $S$ 的一个长度为偶数的连续子串 $T$，然后给这个子串 $T$ 做如下操作：

• 选定 $T$ 的一些位置上的字符，如果这个字符是 ( 则将其变为 )，如果这个字符是 ) 则将其变为 (，通过选定最少的位置使得 $T$ 变成合法括号序列。
• 其中最少的位置的数量记为所需步数。

铃音将会等概率的从所有可能的子串 $T$ 中选择一个，请帮助她求出所需步数的期望。

当然，你可能不会期望，所以本问题中只需要你求出所有可能的子串 $T$ 所需要的操作的所需步数的总和。

Format

Input

第一行一个正整数 $n$，表示字符串 $S$ 的长度。

第二行一个长度为 $n$ 的字符串，表示 $S$。

Output

一行一个非负整数，表示答案。

Samples

7
())()()

13

举例来说，对于子串 ())(，选定第 $3,4$ 个位置改变字符，步数为 $2$，显然不能一步到位。

对于子串 ))()()，选定第 $1$ 个位置改变字符，步数为 $1$，显然不能不改变字符。

见选手下发文件gift/gift2.in

见选手下发文件gift/gift2.ans

该样例满足子任务 $2$ 的限制。

见选手下发文件gift/gift3.in

见选手下发文件gift/gift3.ans

该样例满足子任务 $7$ 的限制。

Limitation

对于 $100\%$ 的数据：$2\leq n\leq 10^6$，且 $S$ 的字符仅可能为 ( 或 )。

特殊性质 A：满足 $n$ 为偶数且 $S$ 前 $\frac{n}{2}$ 个字符为 (，后 $\frac{n}{2}$ 个字符为 )。

特殊性质 B：满足 $n$ 为偶数且 $S$ 由 $\frac{n}{2}$ 个 () 顺次拼接而成。

特殊性质 C：满足 $S$ 中仅包含 (。

数据于 Windows 环境下生成。