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 N 500005
using namespace std;
typedef long long ll;
const int mod1=1e9+7,mod2=1e9+9,C=200017;
int n;
ll bin[2][N],a[N];
char s[N];
map<pair<ll,ll>,int> mp;
pair<ll,ll> g[N];
ll quick_pow(ll a,ll b,const ll mod){
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1) ans=ans*a%mod;
	return ans;
}
int main(){
	scanf("%d",&n);
	scanf("%s",s+1);
	bin[0][0]=bin[1][0]=1;
	for(int i=1;i<=n+n;i++){
		bin[0][i]=bin[0][i-1]*C%mod1;
		bin[1][i]=bin[1][i-1]*C%mod2;
	}
	ll now1=0,now2=0;
	pair<ll,ll> w;
	for(int i=1,pos=n;i<=n;i++){
		if(s[i]=='<') pos--;
		if(s[i]=='>') pos++;
		if(s[i]=='-'){
			a[pos]--;
			now1=(now1-bin[0][pos])%mod1;
			now2=(now2-bin[1][pos])%mod2;
		}
		if(s[i]=='+'){
			a[pos]++;
			now1=(now1+bin[0][pos])%mod1;
			now2=(now2+bin[1][pos])%mod2;
		}
		now1=(now1+mod1)%mod1;
		now2=(now2+mod2)%mod2;
		w=make_pair(now1,now2);
		g[i]=w;
		if(mp.find(w)==mp.end()) mp[w]=0;
		mp[w]++;
	}
	ll ans=mp[w];
	ll inv1=quick_pow(C,mod1-2,mod1),inv2=quick_pow(C,mod2-2,mod2);
	ll w1=1,w2=1,add1=0,add2=0;
	for(int i=1;i<n;i++){
		if(s[i]=='<'){
			w1=w1*inv1%mod1;
			w2=w2*inv2%mod2;
			//add1=add1%mod1;
			//add2=add2*inv2%mod2;
		}
		if(s[i]=='>'){
			w1=w1*C%mod1;
			w2=w2*C%mod2;
			//add1=add1*C%mod1;
			//add2=add2*C%mod2;
		}
		if(s[i]=='+'){
			add1=(add1+bin[0][n]*w1)%mod1;
			add2=(add2+bin[1][n]*w2)%mod2;
		}
		if(s[i]=='-'){
			add1=(add1-bin[0][n]*w1)%mod1;
			add2=(add2-bin[1][n]*w2)%mod2;
		}
		w.first=(g[n].first*w1+add1)%mod1;
		w.second=(g[n].second*w2+add2)%mod2;
		w.first=(w.first+mod1)%mod1;
		w.second=(w.second+mod2)%mod2;
		mp[g[i]]--;
		if(mp.find(w)!=mp.end()) ans+=mp[w];
	}
	printf("%lld\n",ans);
	return 0;
}