分数: 1200 点
问题陈述
在高桥的心中,总有一个长度为整数的序列 2 \times 10^9 + 1: A = (A_{-10^9}, A_{-10^9 + 1}, ..., A_{10^9 - 1}, A_{10^9}) 和一个整数 P.
最初,序列中的所有元素 A 在高桥的脑海里是 0,以及整数的值 P is 0.
当高桥吃符号时 +, -, > 和 <,序列 A 和整数 P 将更改如下:
- 当他吃饭时
+的值 A_P 增加 1; - 当他吃饭时
-的值 A_P 减少 1; - 当他吃饭时
>的值 P 增加 1; - 当他吃饭时
<的值 P 减少 1.
高桥有一根绳子 S 长度 N。中的每个角色 S 是符号之一 +, -, > 和 <。
他选择了一对整数 (i, j) 这样 1 \leq i \leq j \leq N 并吃了那些符号 i-th, (i+1)-th, ..., j- 第一个字符 S,按此顺序。
我们听说,他吃完饭后,顺序 A 变得和他吃掉了所有符号一样 S 从头到尾。
这样的可能对有多少个 (i, j) 有吗?
约束
- 1 \leq N \leq 250000
- |S| = N
- 中的每个字符 S is
+,-,>or<.
输入
输入由标准输入按以下格式给出:
N S
输出
打印答案。
示例输入 1
5 +>+<-
示例输出 1
3
如果高桥吃掉了所有符号 S, A_1 = 1 和所有其他元素将是 0。 成对的 (i, j) 导致相同的序列 A 如下:
- (1, 5)
- (2, 3)
- (2, 4)
示例输入 2
5 +>+-<
示例输出 2
5
请注意,值 P 可能与高桥吃掉所有符号时的值不同 S.
示例输入 3
48 -+><<><><><>>>+-<<>->>><<><<-+<>><+<<>+><-+->><<
示例输出 3
475