Problem: 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.

Examples

Input

5
+>+<-


Output

3


Input

5
+>+-<


Output

5


Input

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


Output

475

Solution (in CPP):

Solution:
#include <cstdio>
#include <unordered_map>

typedef long long LL;
const int Mod[2] = {999988679, 999988609};
const int B[2] = {370728, 370732};
const int iB[2] = {396903752, 462741403};
const int MN = 250005;

inline void Add(int &x, int y, int i) { x -= (x += y) >= Mod[i] ? Mod[i] : 0; }

int N;
char S[MN];
int A[2][MN], D[2][MN];
std::unordered_map<LL, int> Buk;
LL Ans;

int main() {
	scanf("%d%s", &N, S + 1);
	for (int j = 0; j < 2; ++j) A[j][0] = 0, D[j][0] = 1;
	for (int i = 1, V[2] = {1, 1}; i <= N; ++i) {
		for (int j = 0; j < 2; ++j) {
			A[j][i] = A[j][i - 1];
			if (S[i] == '+') Add(A[j][i], V[j], j);
			if (S[i] == '-') Add(A[j][i], Mod[j] - V[j], j);
			if (S[i] == '>') V[j] = (LL)V[j] * B[j] % Mod[j];
			if (S[i] == '<') V[j] = (LL)V[j] * iB[j] % Mod[j];
			D[j][i] = V[j];
		}
	}
	for (int i = N; i >= 0; --i) {
		Ans += Buk[
			(A[0][i] + (LL)A[0][N] * D[0][i]) % Mod[0] +
			(A[1][i] + (LL)A[1][N] * D[1][i]) % Mod[1] * Mod[0]
		];
		++Buk[A[0][i] + (LL)A[1][i] * Mod[0]];
	}
	printf("%lld\n", Ans);
	return 0;
}