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<map>
using namespace std;

typedef long long LL;

struct MyInt64 {
	LL X;
	MyInt64(LL X = 0LL): X(X) {}
};

const LL Base = 1926081719260847LL, BaseInv = 696411651951639283LL, Mod = 999999999999999989LL;

inline bool operator < (MyInt64 P1, MyInt64 P2) {
	return P1.X < P2.X;
}

inline MyInt64 operator + (MyInt64 P1, MyInt64 P2) {
	
	P1.X += P2.X;
	if(P1.X >= Mod)
		P1.X -= Mod;
	
	return P1;
}

inline MyInt64 operator - (MyInt64 P1, MyInt64 P2) {
	
	P1.X -= P2.X;
	if(P1.X < 0)
		P1.X += Mod;
	
	return P1;
}

inline MyInt64& operator += (MyInt64&P1, MyInt64 P2) {
	
	P1.X += P2.X;
	if(P1.X >= Mod)
		P1.X -= Mod;
	
	return P1;
}

inline MyInt64 operator * (MyInt64 P1, MyInt64 P2) {
	
	MyInt64 Ans;
	
	while(P2.X) {
		
		if(P2.X & 1)
			Ans += P1.X;
		
		P2.X >>= 1;
		P1.X <<= 1;
		if(P1.X >= Mod)
			P1.X -= Mod;
		
	}
	
	return Ans;
}

int N;
char str[250005];

MyInt64 H[250005], P[250005];

map<MyInt64, int> MyMap;

LL Ans;

int main() {
	
	scanf("%d", &N);
	scanf("%s", str + 1);
	
	H[0] = MyInt64(0), P[0] = MyInt64(1);
	
	for(int i = 1; i <= N; ++i) {
		
		if(str[i] == '+')
			H[i] = H[i-1] + P[i-1],
			P[i] = P[i-1];
		
		if(str[i] == '-')
			H[i] = H[i-1] - P[i-1],
			P[i] = P[i-1];
		
		if(str[i] == '<')
			H[i] = H[i-1],
			P[i] = P[i-1] * BaseInv;
		
		if(str[i] == '>')
			H[i] = H[i-1],
			P[i] = P[i-1] * Base;
		
//		printf("%lld %lld\n", H[i].X, P[i].X);
		
	}
	
	for(int i = N; i >= 0; --i) {
		
		Ans += MyMap[H[N] * P[i] + H[i]];
		
		++MyMap[H[i]];
		
	}
	
	printf("%lld\n", Ans);
	
	return 0;
}