题目描述

Ivo 正在解决一个由 $N$ 个正确平衡括号组成的字符串问题，但他读东西不太仔细，担心会把某个子串倒着读出来。他想知道：有多少种方式可以把某个非空子串逆序之后，整个字符串仍然保持为正确平衡括号串。

更准确地说，给定一个长度为 $N$ 的字符串，其中每个字符都是 ( 或 )。该字符串是一个正确平衡括号串，也就是说：

• 开括号和闭括号数量相同；
• 每个开括号都对应其右侧某个不同的闭括号；
• 这些括号配对互不交叉。也就是说，如果两对括号分别为 $(A_1, B_1)$ 和 $(A_2, B_2)$，且 $A_1 < A_2$，那么一定满足以下两种情况之一：
  • $A_1 < B_1 < A_2 < B_2$；
  • $A_1 < A_2 < B_2 < B_1$。

Ivo 想知道，有多少个不同的非空子串可以被按字符顺序整体逆序（但单个括号字符本身不翻转），并且使得整个字符串依然是正确平衡括号串。

如果两个子串的左端点 $L$ 和/或右端点 $R$ 不同，那么它们被视为不同的子串。整个字符串本身也算一个子串。

例如，当字符串为 (())() 时，合法的逆序共有 $14$ 种：

• $L = R = 1$，得到 (())()。
• $L = R = 2$，得到 (())()。
• $L = R = 3$，得到 (())()。
• $L = R = 4$，得到 (())()。
• $L = R = 5$，得到 (())()。
• $L = R = 6$，得到 (())()。
• $L = 1, R = 2$，得到 (())()。
• $L = 2, R = 3$，得到 ()()()。
• $L = 3, R = 4$，得到 (())()。
• $L = 4, R = 5$，得到 (()())。
• $L = 3, R = 5$，得到 ((()))。
• $L = 4, R = 6$，得到 (())()。
• $L = 2, R = 5$，得到 (())()。
• $L = 3, R = 6$，得到 (()())。

请编写程序回答 Ivo 的问题，即计算满足条件的子串数量。

输入格式

第一行输入一个整数 $N$，表示字符串长度。
第二行输入一个不含空格的字符串。

输出格式

输出一行一个整数，表示满足条件的子串数量。

数据范围

• $2 \le N \le 4 \times 10^6$

子任务

只有当某个子任务及其之前所有子任务的测试点都通过时，才能获得该子任务的分数。

样例

输入

6
(())()

输出

14