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>

using namespace std;

#define LL long long
#define N 600000

const LL mod1=998244353,mod2=353448299;
LL n,B1,iB1,B2,iB2,ans,pw1[N],ipw1[N],h1[N],pw2[N],ipw2[N],h2[N],p[N];
char s[N];
map<LL,map<LL,LL> > mp;

LL inv1(LL x){return x==1?1:(mod1-mod1/x)*inv1(mod1%x)%mod1;}

LL inv2(LL x){return x==1?1:(mod2-mod2/x)*inv2(mod2%x)%mod2;}

int main(){
	scanf("%lld%s",&n,s+1);
	pw1[0]=ipw1[0]=1; iB1=inv1(B1=233);
	pw2[0]=ipw2[0]=1; iB2=inv2(B2=377);
	for (LL i=1;i<=n*2;++i){
		pw1[i]=pw1[i-1]*B1%mod1;
		ipw1[i]=ipw1[i-1]*iB1%mod1;
		pw2[i]=pw2[i-1]*B2%mod2;
		ipw2[i]=ipw2[i-1]*iB2%mod2;
	}
	p[0]=n;
	for (LL i=1;i<=n;++i){
		if (s[i]=='+'){
			p[i]=p[i-1];
			h1[i]=(h1[i-1]+pw1[p[i]])%mod1;
			h2[i]=(h2[i-1]+pw2[p[i]])%mod2;
		}
		if (s[i]=='-'){
			p[i]=p[i-1];
			h1[i]=(h1[i-1]-pw1[p[i]]+mod1)%mod1;
			h2[i]=(h2[i-1]-pw2[p[i]]+mod2)%mod2;
		}
		if (s[i]=='>'){
			p[i]=p[i-1]+1;
			h1[i]=h1[i-1]; h2[i]=h2[i-1];
		}
		if (s[i]=='<'){
			p[i]=p[i-1]-1;
			h1[i]=h1[i-1]; h2[i]=h2[i-1];
		}
		++mp[h1[i]][h2[i]];
	}
	for (LL i=1;i<=n;++i){
 		LL d=p[i-1]-p[0],t1=h1[n],t2=h2[n];
		if (d>=0){t1=t1*pw1[d]%mod1; t2=t2*pw2[d]%mod2;}
		else{t1=t1*ipw1[-d]%mod1; t2=t2*ipw2[-d]%mod2;}
		t1=(t1+h1[i-1]+mod1)%mod1; t2=(t2+h2[i-1]+mod2)%mod2;
		ans+=mp[t1][t2];
		--mp[h1[i]][h2[i]];
	}
	printf("%lld\n",ans);
	
	return 0;
}