Migrated from Lutece 3001 又一个maco的括号序列

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

（本题来源于真实经历） 本届暑假前集训第一次队内赛 $G$ 题是差分约束括号序列（好题！建议去补）， maco 在给那道题造数据的时候非常懵逼，抓破了脑袋都想不到有什么随机生成大量合法括号序列的好办法，直到 maco 摸索出了一些数学性质。现在， maco 想要考验一下你，看看你能否想到 maco 当时所想的绝妙idea。 下面是本题的题面： 给定一串长度为 $n$ 的合法或不合法的括号序列，这个括号序列保证前括号数量等于后括号数量， maco 现在需要将该括号序列的某个真前缀（长度大于 $0$ 小于 $n$ 的前缀）移动到这个括号序列的末尾，形成一个新的括号序列，希望能够使这个新的括号序列合法。请问 maco 有多少种移动的方法？

Input

第一行是一个偶数 $n$ ，代表括号序列的长度 第二行是一个合法或不合法的括号序列

Output

输出一个整数，代表有多少种移动这个括号序列的方案，如果不存在这样的方案，请输出 $0$

Samples

2
)(

1

2
()

0

Constraints

$2≤n≤10^6$

Note

注：此题不止一种解法，大家可以尝试着分析证明一下这道题背后的数学性质，以至于可以用这种方法来随机生成大量合法括号序列

Resources

2023 UESTC ICPC Training for Math