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 <bits/stdc++.h>

typedef long long int int64;
static const int64 mod1 = 1290382391, mod2 = 1350983507;
using hash = std::pair<int,int>;
hash x(139436098, 325878929);
hash y(1142067043, 890079571);
int64 exgcd(int64 a,int64 b,int64 &c,int64 &d)
{
	if(b == 0) {
		c = 1, d = 0;
		return a;
	}
	int64 k = exgcd(b,a%b,d,c);
	d -= c * (a / b);
	return k;
}
using hash = std::pair<int,int>;
hash operator +(const hash &a, const hash &b) {
	return hash(((int64)a.first+b.first)%mod1,((int64)a.second+b.second)%mod2);
}
hash operator *(const hash &a, const hash &b) {
	return hash((int64)a.first*b.first%mod1,(int64)a.second*b.second%mod2);
}
hash operator -(const hash &a, const hash &b) {
	int v1 = a.first-b.first, v2 = a.second-b.second;
	if(v1<0) v1+=mod1; if(v2<0) v2+=mod2;
	return hash(v1,v2);
}
hash inv(const hash &x) {
	int64 v1,v2,v3,v4;
	assert(exgcd(mod1,x.first,v1,v2) == 1);
	assert(exgcd(mod2,x.second,v3,v4) == 1);
	return hash(v2<0?v2+mod1:v2,v4<0?v4+mod2:v4);
}
hash operator /(const hash &a, const hash &b) {
	return a*inv(b);
}
using line = std::pair<hash,hash>;
// b(a(x))
line compose(const line &a,const line &b) {
	return line(a.first*b.first,b.first*a.second+b.second);
}
int n;
char s[250003];
line pre[250003],invpre[250003];
int main()
{
	scanf("%d %s",&n,s+1);
	pre[n+1] = invpre[n+1] = line(hash(1,1),hash(0,0));
	hash f(0,0);
	for(int i = n;i >= 1;--i) {
		line l, invl;
		switch(s[i]) {
		case '+': {
			l = line(hash(1,1),hash(1,1));
			invl = line(hash(1,1),hash(mod1-1,mod2-1));
			break;
		}
		case '-': {
			l = line(hash(1,1),hash(mod1-1,mod2-1));
			invl = line(hash(1,1),hash(1,1));
			break;
		}
		case '>': {
			l = line(x,hash(0,0));
			invl = line(y,hash(0,0));
			break;
		}
		case '<': {
			l = line(y,hash(0,0));
			invl = line(x,hash(0,0));
			break;
		}}
		pre[i] = compose(pre[i+1],l);
		invpre[i] = compose(invl,invpre[i+1]);
	}
	f = pre[1].second;
	std::map<hash,int> m;
	int64 ans = 0;
	for(int i = n+1;i >= 1;--i) {
		ans += m[f*invpre[i].first+invpre[i].second];
		++m[invpre[i].second];
	}
	printf("%lld\n", ans);
}