You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

[a-z][a-z][a-z]?[a-z]?qwq。

题目描述

定义『合法括号序列』：

• 空串是合法括号序列。
• 若 $\tt A$ 是合法括号序列，则 $\texttt{(A)}$ 是合法括号序列。
• 若 $\tt A, B$ 均为合法括号序列，则 $\texttt{AB}$ 是合法括号序列。

定义『半合法括号序列』包含 $\texttt (, \texttt ), \texttt *$ 三种字符，其中把每个 $\texttt *$ 替换为 $\texttt ($，$\texttt )$ 或空字符串中的一种后，存在至少一种方案使该字符串成为合法括号序列。

给出仅包含 $\texttt (, \texttt ), \texttt *$ 三种字符的字符串 $S$，求 $S$ 的半合法括号序列子串数量。

输入格式

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

第二行一个字符串表示 $S$。

输出格式

一行一个整数表示答案。

样例

7
(*)*(*)

17

数据规模与约定

• 特殊性质 A：保证 $S$ 内不含有字符 $\texttt *$。
• 特殊性质 B：$S$ 的每个字符均匀随机生成。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 2\times 10^5$。