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;

typedef long long ll;
typedef pair<ll,ll> P;

#define fr first
#define sc second

const ll MOD[2] = {1000000007,1000000009};

ll modpow(ll x,ll k,int t){
	if(k==0)return 1;
	ll ret=modpow(x,k/2,t);
	ret*=ret; ret%=MOD[t];
	if(k%2==1){
		ret*=x; ret%=MOD[t];
	}
	return ret;
}

int main(){
	int n;
	string s;
	cin>>n>>s;
	
	srand((unsigned)time(NULL));
	ll r[2]={rand()+n,rand()+n};
	
	P hash[250010],h=P(0,0);
	ll loc[250010],p=0;
	for(int i=0;i<n;i++){
		if(s[i]=='+'){
			h.fr+=modpow(r[0],p+MOD[0]-1,0);
			if(h.fr>=MOD[0])h.fr-=MOD[0];
			h.sc+=modpow(r[1],p+MOD[1]-1,1);
			if(h.sc>=MOD[1])h.sc-=MOD[1];
		}
		else if(s[i]=='-'){
			h.fr+=MOD[0]-modpow(r[0],p+MOD[0]-1,0);
			if(h.fr>=MOD[0])h.fr-=MOD[0];
			h.sc+=MOD[1]-modpow(r[1],p+MOD[1]-1,1);
			if(h.sc>=MOD[1])h.sc-=MOD[1];
		}
		else if(s[i]=='>'){
			p++;
		}
		else {
			p--;
		}
		hash[i]=h;
		loc[i]=p;
	}
	
	ll ret=0;
	map<P,ll> cnt;
	for(int i=n-1;i>=0;i--){
		P nex=hash[i];
		P dif=hash[n-1];
		dif.fr*=modpow(r[0],loc[i]+MOD[0]-1,0); dif.fr%=MOD[0];
		dif.sc*=modpow(r[1],loc[i]+MOD[1]-1,1); dif.sc%=MOD[1];
		nex.fr+=dif.fr; nex.fr%=MOD[0];
		nex.sc+=dif.sc; nex.sc%=MOD[1];
		ret+=cnt[nex];
		cnt[hash[i]]++;
	}
	cout<<ret+cnt[hash[n-1]]<<endl;
}