AT_arc099_d.[ARC099F] Eating Symbols Hard

高桥君脑海中总是浮现着一个长度为 $2 \times 10^9 + 1$ 的整数序列 $A = (A_{-10^9}, A_{-10^9 + 1}, \ldots, A_{10^9 - 1}, A_{10^9})$，以及一个整数 $P$。

一开始，整数序列 $A$ 的所有元素都是 $0$，整数 $P$ 的值也是 $0$。

每当高桥君吃下一个符号 +、-、> 或 < 时，脑海中的整数序列 $A$ 和整数 $P$ 会发生如下变化：

• 吃下 + 时，$A_P$ 的值加 $1$。
• 吃下 - 时，$A_P$ 的值减 $1$。
• 吃下 > 时，$P$ 的值加 $1$。
• 吃下 < 时，$P$ 的值减 $1$。

高桥君有一个长度为 $N$ 的字符串 $S$，其中每个字符都是 +、-、> 或 < 之一。高桥君可以选择一组整数 $(i, j)$，满足 $1 \leq i \leq j \leq N$，然后依次吃下 $S$ 的第 $i$ 到第 $j$ 个字符。若吃完后脑海中的整数序列 $A$ 与高桥君从第 $1$ 个字符开始顺序吃完 $S$ 的所有符号后得到的 $A$ 完全相同，则称该组 $(i, j)$ 是可行的。

请计算有多少组 $(i, j)$ 是可行的。

输入从标准输入读取，格式如下：

$N$ $S$

请输出答案。

限制条件

• $1 \leq N \leq 250000$
• $|S| = N$
• $S$ 的每个字符都是 +、-、> 或 < 之一

样例解释 1

高桥君吃完 $S$ 的所有符号后，$A_1 = 1$，其余 $A$ 的元素全为 $0$。使 $A$ 与此相等的 $(i, j)$ 有以下几组：

• $(1, 5)$
• $(2, 3)$
• $(2, 4)$

样例解释 2

注意，即使 $P$ 与高桥君吃完 $S$ 的所有符号后得到的 $P$ 不同，也没有关系。

由 ChatGPT 4.1 翻译