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>

#define y1 dmytxdy
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int cys=1000000007,N=50;
int n;
ll a[250005],b[250005],pw[250005],ipw[250005],ans[250005];
unordered_map<ll,ll> bk;
char s[250005];

ll mod(ll x){return x>=cys?x-cys:x;}

ll qpow(ll x,ll p){
	ll ret=1;
	for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
	return ret;
}

int main(){
	n=readint();
	scanf("%s",s+1);
	for(int i=1;i<=n;i++) b[i]=b[i-1]+(s[i]=='>')-(s[i]=='<');
	memset(ans,0x3f,sizeof(ans));
	for(int ct=1;ct<=N;ct++){
		ll ax=(1ll*rand()*RAND_MAX+rand())%cys,bx=qpow(ax,cys-2),p=1,now=0;
		pw[0]=ipw[0]=1;
		for(int i=1;i<=n;i++) pw[i]=pw[i-1]*ax%cys;
		for(int i=1;i<=n;i++) ipw[i]=ipw[i-1]*bx%cys;
		for(int i=1;i<=n;i++){
			if(s[i]=='+') now=mod(now+p);
			else if(s[i]=='-') now=mod(now+cys-p);
			else if(s[i]=='<') p=p*bx%cys;
			else if(s[i]=='>') p=p*ax%cys;
		}
		a[n+1]=0;
		for(int i=n;i>=1;i--){
			if(s[i]=='+') a[i]=mod(a[i+1]+1);
			else if(s[i]=='-') a[i]=mod(a[i+1]+cys-1);
			else if(s[i]=='<') a[i]=a[i+1]*bx%cys;
			else if(s[i]=='>') a[i]=a[i+1]*ax%cys;
		}
		for(int i=1;i<=n;i++) a[i]=a[i]*(b[i-1]>0?pw[b[i-1]]:ipw[-b[i-1]])%cys;
		bk.clear();
		bk[0]++;
		for(int i=n;i>=1;i--){
			chkmin(ans[i],bk[mod(a[i]+cys-now*(b[i-1]>0?pw[b[i-1]]:ipw[-b[i-1]])%cys)]);
			bk[a[i]]++;
		}
		if(1.0*clock()/CLOCKS_PER_SEC>1.9) break;
	}
	ll res=0;
	for(int i=1;i<=n;i++) res+=ans[i];
	printf("%lld\n",res);
	return 0;
}