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<cmath>
#include<algorithm>
#include<cstring>
#include<map>
#define maxn 250005
#define ll long long 
using namespace std;

const int M1=1000000007,mo1=998244353,M2=19260817,mo2=1000000007,maxh=19260817;
int n,i,j,k,a[maxn];char ch;ll hs[maxh][3],ans;
struct hash{
	ll M,mo,s[maxn],c[maxn],mul[maxn],inv[maxn],invM;
	ll cm(int k){return (k<0)?inv[-k]:mul[k];}
	ll ksm(ll x,ll y){
		ll s=1;
		for(;y;y/=2,x=x*x%mo) if (y&1)
			s=s*x%mo;
		return s;
	}
	void prepare(){
		mul[0]=1;for(i=1;i<=n;i++) mul[i]=mul[i-1]*M%mo;
		inv[0]=1,invM=ksm(M,mo-2);for(i=1;i<=n;i++) inv[i]=inv[i-1]*invM%mo; 
		for(int i=n;i>=1;i--) {
			c[i]=c[i+1];
			if (a[i]=='<') s[i]=s[i+1]*M%mo,c[i]++; else 
			if (a[i]=='>') s[i]=s[i+1]*invM%mo,c[i]--; else 
			if (a[i]=='+') s[i]=(s[i+1]+1)%mo; else s[i]=(s[i+1]+mo-1)%mo;
		}		
	}
	ll get(int x){return (s[i]-s[1]+mo)*cm(-c[i])%mo;}
	ll get2(int x){return s[i]*cm(-c[i])%mo;}
} hs1,hs2;

void add(ll x,ll y){
	ll i=(x*23333333+y)%maxh;
	while (hs[i][2]&&(hs[i][0]!=x||hs[i][1]!=y))
		i=(i+1)%maxh;
	hs[i][0]=x,hs[i][1]=y,hs[i][2]++;
}
ll sum(ll x,ll y){
	ll i=(x*23333333+y)%maxh;
	while (hs[i][2]&&(hs[i][0]!=x||hs[i][1]!=y))
		i=(i+1)%maxh;
	return hs[i][2];
}

int main(){
	scanf("%d",&n),ch=getchar();
	while (ch!='<'&&ch!='>'&&ch!='+'&&ch!='-') ch=getchar();
	for(i=1;i<=n;i++) a[i]=ch,ch=getchar();
	hs1.M=M1,hs1.mo=mo1,hs2.M=M2,hs2.mo=mo2;
	hs1.prepare(),hs2.prepare();
	add(0,0);
	for(i=n;i>=1;i--){
		ll v1=hs1.get(i),v2=hs2.get(i);
		ans+=sum(v1,v2);
		add(hs1.get2(i),hs2.get2(i));
	}
//	for(i=1;i<=n;i++) for(j=i+1;j<=n+1;j++)
//		if (((s[i]-s[j]*cm(c[i]-c[j])%mo)%mo+mo)%mo==s[1])
//			ans++;
//	printf("%lld\n",ans),ans=0;
//	for(i=n;i>=1;i--) {
//		ll v=(s[i]-s[1]+mo)*cm(-c[i])%mo;
//		if (S.find(v)!=S.end()) 
//			ans+=S[v];
//		S[s[i]*cm(-c[i])%mo]++;
//	}
	printf("%lld",ans);
}