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
#define p1 19260817
#define p2 19491001
#define m1 666623333
#define m2 1004535809
using namespace std;
int head[1048577],nxt[500005],tot=0;
int w1[500005],w2[500005],w[500005];
int a1[250005],b1[250005];
int a2[250005],b2[250005];
char s[250005];
ll ans=0;
inline int qpow(int a,int b,int mod)
{int res=1,tp=a;
while (b)
{if (b&1) res=1ll*res*tp%mod;
tp=1ll*tp*tp%mod;b>>=1;
}
return res;
}
inline void add(int v1,int v2)
{int bel=(1ll*v1*p1+v2)&1048575,i;
for (i=head[bel];i;i=nxt[i])
{if (w1[i]==v1&&w2[i]==v2) {w[i]++;return;}
}
tot++;nxt[tot]=head[bel];head[bel]=tot;
w1[tot]=v1;w2[tot]=v2;w[tot]=1;
}
inline int ask(int v1,int v2)
{int bel=(1ll*v1*p1+v2)&1048575,i;
for (i=head[bel];i;i=nxt[i])
{if (w1[i]==v1&&w2[i]==v2) return w[i];
}
return 0;
}
inline int sub1(int a,int b)
{return (a-b<0?a-b+m1:a-b);}
inline int sub2(int a,int b)
{return (a-b<0?a-b+m2:a-b);}
inline int add1(int a,int b)
{return (a+b>=m1?a+b-m1:a+b);}
inline int add2(int a,int b)
{return (a+b>=m2?a+b-m2:a+b);}
int main (){
	int i,n,x1=0,x2=0;
	scanf ("%d",&n);
	scanf ("%s",s+1);
	a1[n+1]=1;b1[n+1]=0;
	a2[n+1]=1;b2[n+1]=0;
	int inv1=qpow(p1,m1-2,m1);
	int inv2=qpow(p2,m2-2,m2);
	for (i=n;i>=1;i--)
	{if (s[i]=='<') 
	{a1[i]=1ll*a1[i+1]*p1%m1;
	a2[i]=1ll*a2[i+1]*p2%m2;
	b1[i]=b1[i+1];b2[i]=b2[i+1];
	continue;
	}
	if (s[i]=='>')
	{a1[i]=1ll*a1[i+1]*inv1%m1;
	a2[i]=1ll*a2[i+1]*inv2%m2;
	b1[i]=b1[i+1];b2[i]=b2[i+1];
	continue;
	}
	if (s[i]=='+')
	{b1[i]=sub1(b1[i+1],a1[i+1]);
	b2[i]=sub2(b2[i+1],a2[i+1]);
	a1[i]=a1[i+1];a2[i]=a2[i+1];
	continue;
	}
	b1[i]=add1(b1[i+1],a1[i+1]);
	b2[i]=add2(b2[i+1],a2[i+1]);
	a1[i]=a1[i+1];a2[i]=a2[i+1];
	}
	for (i=n;i>=1;i--)
	{if (s[i]=='+') {x1=add1(x1,1);x2=add2(x2,1);continue;}
	if (s[i]=='-') {x1=sub1(x1,1);x2=sub2(x2,1);continue;}
	if (s[i]=='<') {x1=1ll*x1*inv1%m1;x2=1ll*x2*inv2%m2;continue;}
	x1=1ll*x1*p1%m1;x2=1ll*x2*p2%m2;
	}
	add(0,0);
	for (i=n;i>=1;i--)
	{int r1=(1ll*a1[i]*x1+b1[i])%m1;
	int r2=(1ll*a2[i]*x2+b2[i])%m2;
	ans+=ask(r1,r2);
	add(b1[i],b2[i]);
	}
	printf ("%lld\n",ans);
	return 0;
}