[ARC099F] Eating Symbols Hard

你有一个初始为 $0$ 的数组和一个初始在 $0$ 的指针，范围可以看做无限。 给出一个长度为 $N$ 的操作串，由 `<`，`>`，`+`，`-` 组成，其中每个字符意义如下。 - `<` 将指针左移一位。 - `>` 将指针右移一位。 - `+` 将指针对应位置 $+1$。 - `- ` 将指针对应位置 $-1$。 求有多少个子串，使得执行完子串的操作后，数组和执行完整个串是一样的。 $1 \leq N \leq 250000$。

[problemUrl]: https://atcoder.jp/contests/arc099/tasks/arc099_d 高橋君は，いつも頭の中に，長さ $ 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 $

答えを出力せよ．

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 $ が異なっていてもかまわないことに注意してください．