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 rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=500005;
const int hval[4]={12345678,23456781,34567812,45678123};
const int mod[4]={515880193,998244353,int(1e9+7),int(1e9+9)};
class Hash{
public:
	int h[4];
	Hash(){memset(h,0,sizeof(h));}
	bool operator < (const Hash &o)const{
		if(h[0]!=o.h[0])return h[0]<o.h[0];
		if(h[1]!=o.h[1])return h[1]<o.h[1];
		if(h[2]!=o.h[2])return h[2]<o.h[2];
		return h[3]<o.h[3];
	}
	Hash operator + (const Hash &o)const{
		Hash res;
		rep(i,4){
			res.h[i]=h[i]+o.h[i];
			if(res.h[i]>=mod[i])res.h[i]-=mod[i];
		}
		return res;
	}
	Hash operator - (const Hash &o)const{
		Hash res;
		rep(i,4){
			res.h[i]=h[i]-o.h[i];
			if(res.h[i]<0)res.h[i]+=mod[i];
		}
		return res;
	}
	Hash operator * (const Hash &o)const{
		Hash res;
		rep(i,4)res.h[i]=1LL*h[i]*o.h[i]%mod[i];
		return res;
	}
}H,iH,one,pw[maxn],ipw[maxn],sum[maxn];
int n;
int pos[maxn];
map<Hash,int>cnt;
char s[maxn];

int power(int x,int pow,int mod){
	int res=1;
	for(;pow;pow>>=1){
		if(pow&1)res=1LL*res*x%mod;
		x=1LL*x*x%mod;
	}
	return res;
}

int main(){
	scanf("%d%s",&n,s+1);
	rep(i,4){
		H.h[i]=hval[i];
		iH.h[i]=power(hval[i],mod[i]-2,mod[i]);
		one.h[i]=1;
	}
	pw[0]=ipw[0]=one;
	REP(i,2*n){
		pw[i]=pw[i-1]*H;
		ipw[i]=ipw[i-1]*iH;
	}
	REP(i,n){
		pos[i]=pos[i-1];
		sum[i]=sum[i-1];
		if(s[i]=='<')pos[i]--;
		else if(s[i]=='>')pos[i]++;
		else if(s[i]=='+')sum[i]=sum[i]+pw[pos[i]+n];
		else sum[i]=sum[i]-pw[pos[i]+n];
	}
	ll ans=0;
	for(int i=n;i>=1;i--){
		cnt[sum[i]]++;
		if(pos[i-1]<0)ans+=cnt[(sum[n]*ipw[-pos[i-1]])+sum[i-1]];
		else ans+=cnt[(sum[n]*pw[pos[i-1]])+sum[i-1]];
	}
	printf("%lld\n",ans);
	return 0;
}