问题描述

在Takahashi的脑海中，始终存在一个长度为$2 \times 10^9 + 1$的整数序列：$A = (A_{-10^9}, A_{-10^9 + 1}, ..., A_{10^9 - 1}, A_{10^9})$，以及一个整数$P$。

最初，Takahashi心中的序列$A$中的所有元素都为0，整数$P$的值为0。

当Takahashi吃掉符号+、-、>和<时，序列$A$和整数$P$的变化如下：

• 当他吃掉+时，$A_P$的值增加1；
• 当他吃掉-时，$A_P$的值减少1；
• 当他吃掉>时，$P$的值增加1；
• 当他吃掉<时，$P$的值减少1。

Takahashi有一个长度为$N$的字符串$S$。$S$中的每个字符都是+、-、>和<中的一个符号。他选择了一对整数$(i, j)$，使得$1 \leq i \leq j \leq N$，并按照这个顺序吃掉了字符串$S$中第$i$个、$(i + 1)$个、$...$、第$j$个字符。我们听说，在他吃完后，序列$A$的结果与他按顺序吃掉字符串$S$中的所有符号完全一样。有多少种这样可能的$(i, j)$对？

约束条件

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

输入

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

$N$ $S$

输出

输出答案。

示例输入 1

5
+>+<-

示例输出 1

3

如果Takahashi吃掉$S$中的所有符号，$A_1 = 1$，其他所有元素都为0。导致序列$A$相同的$(i, j)$对如下所示：

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

示例输入 2

5
+>+-<

示例输出 2

5

注意，Takahashi吃完$S$中的所有符号后，整数$P$的值可能不同。

示例输入 3

48
-+><<><><><>>>+-<<>->>><<><<-+<>><+<<>+><-+->><<

示例输出 3

475