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 <cstring>
#include <algorithm>
#include <cstdlib>
#include <map>
using namespace std;
typedef long long ll;
#define GG puts("FUCK")
#define N 500050
#define mr(x,y) make_pair(x,y)
inline char nc() {
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd() {
	int x=0; char s=nc();
	while(s<'0'||s>'9') s=nc();
	while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=nc();
	return x;
}
char rc() {
	char s=nc();
	while(s!='+'&&s!='-'&&s!='>'&&s!='<') s=nc();
	return s;
}
int mod1=998244353,base1=19260817,inv1;
int mod2=353448299,base2=20000003,inv2;
int h1[N],mi1[N],imi1[N],p[N],n,C;
int h2[N],mi2[N],imi2[N];
map<pair<int,int>,int>mp;
int qp(int x,int y,int p) {
	int re=1;
	for(;y;y>>=1,x=ll(x)*x%p) if(y&1) re=ll(re)*x%p;
	return re;
}
int main() {
	inv1=qp(base1,mod1-2,mod1);
	inv2=qp(base2,mod2-2,mod2);
	n=rd(); char str;
	int i;
	for(mi1[0]=imi1[0]=mi2[0]=imi2[0]=i=1;i<=(n<<1);i++) {
		mi1[i]=ll(mi1[i-1])*base1%mod1;
		imi1[i]=ll(imi1[i-1])*inv1%mod1;
		mi2[i]=ll(mi2[i-1])*base2%mod2;
		imi2[i]=ll(imi2[i-1])*inv2%mod2;
	}
	p[0]=n;
	for(i=1;i<=n;i++) {
		str=rc();
		if(str=='+') {
			p[i]=p[i-1];
			h1[i]=(h1[i-1]+mi1[p[i]])%mod1;
			h2[i]=(h2[i-1]+mi2[p[i]])%mod2;
		}else if(str=='-') {
			p[i]=p[i-1];
			h1[i]=(h1[i-1]-mi1[p[i]]+mod1)%mod1;
			h2[i]=(h2[i-1]-mi2[p[i]]+mod2)%mod2;
		}else if(str=='>') {
			p[i]=p[i-1]+1;
			h1[i]=h1[i-1]; h2[i]=h2[i-1];
		}else {
			p[i]=p[i-1]-1;
			h1[i]=h1[i-1]; h2[i]=h2[i-1];
		}
		mp[mr(h1[i],h2[i])]++;
	}
	ll ans=0;
	for(i=1;i<=n;i++) {
		int d=p[i-1]-n,t1=h1[n],t2=h2[n];
		if(d>=0) t1=ll(t1)*mi1[d]%mod1,t2=ll(t2)*mi2[d]%mod2;
		else t1=ll(t1)*imi1[-d]%mod1,t2=ll(t2)*imi2[-d]%mod2;
		t1=(t1+h1[i-1])%mod1;
		t2=(t2+h2[i-1])%mod2;
		ans+=mp[mr(t1,t2)];
		mp[mr(h1[i],h2[i])]--;
	}
	printf("%lld\n",ans);
}