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 fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define mod 1000000007
#define Mod 1000000005
#define ll long long
//#define file
using namespace std;

ll p[250001],P[250001],pp[250001],PP[250001],hs[250001],Hs[250001],s,S,p1,p2,p3,p4,ans;
int sum[250001],n,i,j,k,l;
char st[250001];
map<pair<int,int>,int> mp;
map<pair<int,int>,int> :: iterator I;

ll qpower(ll a,int b) {ll ans=1; while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;}
ll Pow(int t) {return (t>=0)?p[t]:P[-t];}
ll Pow2(int t) {return (t>=0)?pp[t]:PP[-t];}

int main()
{
	#ifdef file
	freopen("arc099f.in","r",stdin);
	#endif
	
	scanf("%d",&n);
	scanf("%s",st+1);
	p1=123456789,p2=qpower(p1,Mod);
	p3=114514191,p4=qpower(p3,Mod);
	p[0]=P[0]=pp[0]=PP[0]=1;
	fo(i,1,n) p[i]=p[i-1]*p1%mod,P[i]=P[i-1]*p2%mod,pp[i]=pp[i-1]*p3%mod,PP[i]=PP[i-1]*p4%mod;
	
	fd(i,n,1)
	{
		switch (st[i])
		{
			case '>':{sum[i]=1,s=s*p1%mod;break;}
			case '<':{sum[i]=-1,s=s*p2%mod;break;}
			case '+':{s=(s+1)%mod;break;}
			case '-':{s=(s-1)%mod;break;}
		}
		s=(s+mod)%mod;
		hs[i]=s;
	}
	s=0;
	fd(i,n,1)
	{
		switch (st[i])
		{
			case '>':{sum[i]=1,s=s*p3%mod;break;}
			case '<':{sum[i]=-1,s=s*p4%mod;break;}
			case '+':{s=(s+1)%mod;break;}
			case '-':{s=(s-1)%mod;break;}
		}
		s=(s+mod)%mod;
		Hs[i]=s;
	}
	fo(i,1,n) sum[i]+=sum[i-1];
	
	mp[pair<int,int>(0,0)]=1;
	fd(i,n,1)
	{
		s=((hs[i]-hs[1])*Pow(sum[i-1])%mod+mod)%mod;
		S=((Hs[i]-Hs[1])*Pow2(sum[i-1])%mod+mod)%mod;
		I=mp.find(pair<int,int>(s,S));
		if (I!=mp.end())
		ans+=I->second;
		++mp[pair<int,int>(hs[i]*Pow(sum[i-1])%mod,Hs[i]*Pow2(sum[i-1])%mod)];
	}
	printf("%lld\n",ans);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}