← 返回题目列表

AtCoder · arc099_d

F. 吃符号很难

中文机器翻译题面 查看原题

分数: 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