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 ll long long
using namespace std;
const int N = 501000,mod2 = 1000000007,mod1 = 998244353;
ll *p1,_p1[N],*p2,_p2[N],h1[N],h2[N];
int W[N],n;
char s[N];
map<pair<ll,ll>,int> mp;
ll fp(ll a,ll k,ll mod){
	ll ans=1;
	for(;k;k>>=1,a=a*a%mod)
		if(k&1) ans=a*ans%mod;
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	cin>>s+1;
	p1=_p1+n+10;p1[-n]=1;
	for(int i=-n+1;i<=n;i++) p1[i]=p1[i-1]*434783%mod1;
	p2=_p2+n+10;p2[-n]=1;
	for(int i=-n+1;i<=n;i++) p2[i]=p2[i-1]*434783%mod2;
	ll hsh1=0,hsh2=0;
	int w=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='<') w--;
		if(s[i]=='>') w++;
		W[i]=w;
		if(s[i]=='+'){
			h1[i]=p1[w];h2[i]=p2[w];
			hsh1=(hsh1+p1[w])%mod1;
			hsh2=(hsh2+p2[w])%mod2;
		}
		if(s[i]=='-'){
			h1[i]=mod1-p1[w];
			h2[i]=mod2-p2[w];
			hsh1=(hsh1-p1[w]+mod1)%mod1;
			hsh2=(hsh2-p2[w]+mod2)%mod2;
		}
		mp[make_pair(hsh1,hsh2)]++;
	}
	ll now1=0,now2=0,ans=0;
	for(int i=1;i<=n;i++){
		if(W[i-1]>0) ans+=mp[make_pair((hsh1*fp(434783,W[i-1],mod1)+now1)%mod1,(hsh2*fp(434783,W[i-1],mod2)+now2)%mod2)];
		else ans+=mp[make_pair((hsh1*fp(743624691,-W[i-1],mod1)+now1)%mod1,(hsh2*fp(620380746,-W[i-1],mod2)+now2)%mod2)];
		if(s[i]=='-'||s[i]=='+') now1=(now1+h1[i])%mod1,now2=(now2+h2[i])%mod2;
		mp[make_pair(now1,now2)]--;
	}
	cout<<ans<<'\n';
	return 0;
}