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;
#define N 500050
int mod1=998244353,base1=19260817,inv1;
int mod2=353448299,base2=20000003,inv2;
int h1[N],mi1[N],imi1[N],p[N],n,C;
int h2[N],mi2[N],imi2[N];
map<pair<int,int>,int>mp;
int pw(int x,int y,int p){int r=1;for(;y;y>>=1,x=1ll*x*x%p)if(y&1)r=1ll*r*x%p;return r;}
char ss[N],str;
int main()
{
	inv1=pw(base1,mod1-2,mod1);
	inv2=pw(base2,mod2-2,mod2);
	scanf("%d",&n);
	int i;
	for(mi1[0]=imi1[0]=mi2[0]=imi2[0]=i=1;i<=(n<<1);i++)
	{
		mi1[i]=ll(mi1[i-1])*base1%mod1;
		imi1[i]=ll(imi1[i-1])*inv1%mod1;
		mi2[i]=ll(mi2[i-1])*base2%mod2;
		imi2[i]=ll(imi2[i-1])*inv2%mod2;
	}
	scanf("%s",ss+1);
	p[0]=n;
	for(i=1;i<=n;i++)
	{
		str=ss[i];
		if(str=='+'){p[i]=p[i-1];h1[i]=(h1[i-1]+mi1[p[i]])%mod1;h2[i]=(h2[i-1]+mi2[p[i]])%mod2;}
		else if(str=='-'){p[i]=p[i-1];h1[i]=(h1[i-1]-mi1[p[i]]+mod1)%mod1;h2[i]=(h2[i-1]-mi2[p[i]]+mod2)%mod2;}
		else if(str=='>'){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(i=1;i<=n;i++)
	{
		int d=p[i-1]-n,t1=h1[n],t2=h2[n];
		if(d>=0) t1=ll(t1)*mi1[d]%mod1,t2=ll(t2)*mi2[d]%mod2;
		else t1=ll(t1)*imi1[-d]%mod1,t2=ll(t2)*imi2[-d]%mod2;
		t1=(t1+h1[i-1])%mod1;t2=(t2+h2[i-1])%mod2;
		ans+=mp[make_pair(t1,t2)];
		mp[make_pair(h1[i],h2[i])]--;
	}
	printf("%lld\n",ans);
	return 0;
}