200993: [AtCoder]ARC099 F - Eating Symbols Hard

Problem Statement

In Takahashi's mind, there is always an integer sequence of length $2 \times 10^9 + 1$: $A = (A_{-10^9}, A_{-10^9 + 1}, ..., A_{10^9 - 1}, A_{10^9})$ and an integer $P$.

Initially, all the elements in the sequence $A$ in Takahashi's mind are $0$, and the value of the integer $P$ is $0$.

When Takahashi eats symbols +, -, > and <, the sequence $A$ and the integer $P$ will change as follows:

• When he eats +, the value of $A_P$ increases by $1$;
• When he eats -, the value of $A_P$ decreases by $1$;
• When he eats >, the value of $P$ increases by $1$;
• When he eats <, the value of $P$ decreases by $1$.

Takahashi has a string $S$ of length $N$. Each character in $S$ is one of the symbols +, -, > and <. He chose a pair of integers $(i, j)$ such that $1 \leq i \leq j \leq N$ and ate the symbols that are the $i$-th, $(i+1)$-th, $...$, $j$-th characters in $S$, in this order. We heard that, after he finished eating, the sequence $A$ became the same as if he had eaten all the symbols in $S$ from first to last. How many such possible pairs $(i, j)$ are there?

Constraints

• $1 \leq N \leq 250000$
• $|S| = N$
• Each character in $S$ is +, -, > or <.

Input

Input is given from Standard Input in the following format:

$N$
$S$

Output

Print the answer.

Sample Input 1

5
+>+<-

Sample Output 1

3

If Takahashi eats all the symbols in $S$, $A_1 = 1$ and all other elements would be $0$. The pairs $(i, j)$ that leads to the same sequence $A$ are as follows:

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

Sample Input 2

5
+>+-<

Sample Output 2

5

Note that the value of $P$ may be different from the value when Takahashi eats all the symbols in $S$.

Sample Input 3

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

Sample Output 3

475