区间翻转

题目描述

给定一个长度为 $n$、仅由字符 ( 和 ) 组成的字符串 $s$。

你需要选择一个非空区间 \([l,r]\)，并将区间内的每个括号反转：

• ( 变为 )；
• ) 变为 (。

若操作后的整个字符串是合法括号序列，则称区间 $[l,r]$ 是合法的。

一个括号序列合法，当且仅当：

1. 任意前缀中，左括号数量不少于右括号数量；
2. 整个字符串中，左括号与右括号数量相等。

求合法区间的数量。

输入格式

从文件 invert.in 中读入数据。

第一行一个整数 $n$。

第二行一个长度为 $n$ 的括号字符串 $s$。

输出格式

输出到文件 invert.out 中。

输出一个整数，表示合法区间的数量。

样例

输入：

4
()()

输出：

1

数据规模与约定

对于所有数据：

• $1 \le n \le 10^6$；
• 字符串仅包含 ( 和 )。
• 原始字符串 $s$ 是合法括号序列。

本题采用子任务测试。