题目描述

高橋君は，いつも頭の中に，長さ $2\ \times\ 10^9\ +\ 1$ の整数列 $ A\ =\ (A_{-10^9},\ A_{-10^9\ +\ 1},\ ...,\ 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$ を持っています．$S$ の各文字は +, -, >, < の記号のいずれかです． 高橋君は，$1\ \leq\ i\ \leq\ j\ \leq\ N$ なる整数の組 $(i,\ j)$ を選んで，$S$ の $i,\ i+1,\ ...,\ j$ 文字目の記号をこの順に食べました． 高橋君が記号を食べ終わった後，高橋君が思い浮かべている整数列 $A$ は，高橋君が $S$ のすべての記号を $1$ 文字目から順に食べた場合と等しくなったといいます． このような $(i,\ j)$ として考えられるものは何通りあるか求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $S$

输出格式

答えを出力せよ．

题目大意

你有一个初始为 $0$ 的数组和一个初始在 $0$ 的指针，范围可以看做无限。

给出一个长度为 $N$ 的操作串，由 <，>，+，- 组成，其中每个字符意义如下。

• < 将指针左移一位。
• > 将指针右移一位。
• + 将指针对应位置 $+1$。
• - 将指针对应位置 $-1$。

求有多少个子串，使得执行完子串的操作后，数组和执行完整个串是一样的。

$1 \leq N \leq 250000$。

5
+>+<-

3

5
+>+-<

5

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

475

提示

制約

• $1\ \leq\ N\ \leq\ 250000$
• $|S|\ =\ N$
• $S$ の各文字は +, -, >, < のいずれか

Sample Explanation 1

高橋君が $S$ のすべての記号を食べた場合，$A_1\ =\ 1$ で，$A$ の他の要素はすべて $0$ になります． $A$ がこれと等しくなるような $(i,\ j)$ は次の通りです： - $(1,\ 5)$ - $(2,\ 3)$ - $(2,\ 4)$

Sample Explanation 2

高橋君が $S$ のすべての記号を食べた場合と $P$ が異なっていてもかまわないことに注意してください．