配点 : $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$ の値は $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)$ として考えられるものは何通りあるか求めてください．

制約

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

入力

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

$N$

$S$

出力

答えを出力せよ．

5
+>+<-

3

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

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

5
+>+-<

5

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

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

475