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;
const int N=500005;
typedef long long ll;
ll base1=27,ms1=73939133,inv1;
ll base2=63,ms2=998244353,inv2;
ll h1[N],h2[N],m1[N],im1[N],p[N],m2[N],im2[N];
map<pair<int,int>,int>mp;
char s[N];
ll ksm(ll x,ll k,ll ms){
	ll t=1;
	for (;k;k>>=1){
		if (k&1) t=(t*x)%ms;
		x=(x*x)%ms;
	}
	return t;
}
int main(){
	inv1=ksm(base1,ms1-2,ms1);
	inv2=ksm(base2,ms2-2,ms2);
	int n; 
	scanf("%d",&n);
	m1[0]=m2[0]=im1[0]=im2[0]=1;
	for (int i=1;i<=n*2;i++){
		m1[i]=m1[i-1]*base1%ms1;
		m2[i]=m2[i-1]*base2%ms2;
		im1[i]=im1[i-1]*inv1%ms1;
		im2[i]=im2[i-1]*inv2%ms2;
	}
	p[0]=n;
	scanf("%s",s+1);
	for (int i=1;i<=n;i++){
		if (s[i]=='+'){
			p[i]=p[i-1]; 
			h1[i]=(h1[i-1]+m1[p[i]])%ms1;
			h2[i]=(h2[i-1]+m2[p[i]])%ms2;
		}else if (s[i]=='-'){
			p[i]=p[i-1];
			h1[i]=(h1[i-1]+ms1-m1[p[i]])%ms1;
			h2[i]=(h2[i-1]+ms2-m2[p[i]])%ms2;
		}else if (s[i]=='>'){
			p[i]=p[i-1]+1;
			h1[i]=h1[i-1]; h2[i]=h2[i-1];
		}else{
			p[i]=p[i-1]-1;
			h1[i]=h1[i-1]; h2[i]=h2[i-1];
		}
		mp[make_pair(h1[i],h2[i])]++;
	}
	ll ans=0;
	for (int i=1;i<=n;i++){
		int d=p[i-1]-n;
	    ll t1=h1[n],t2=h2[n];
		if (d>=0){ t1=t1*m1[d]%ms1; t2=t2*m2[d]%ms2;}
		else t1=t1*im1[-d]%ms1,t2=t2*im2[-d]%ms2;
		t1=(t1+h1[i-1])%ms1; t2=(t2+h2[i-1])%ms2;
		ans+=mp[make_pair(t1,t2)];
		mp[make_pair(h1[i],h2[i])]--;	
	}
	printf("%lld\n",ans);
	return 0;
}