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 inf 0x3f3f3f3f
#define m_k make_pair
#define p1 1000000007
#define p2 91815541
#define base 517619
#define delta 250001
#define ll long long
using namespace std;
const int N=250100;
int n,pos,a[N*2],l,r;
ll ans;
char s[N];
struct Hash
{
	ll a,b;
	void print()
	{
		printf("%lld %lld\n",a,b);
	}
}z[N*2];
Hash h[N*2],now,add;
map <Hash,int> mp;
inline ll m_pow(ll a,int b,int mod)
{
	ll ans=1;
	while (b)
	{
		if (b&1) ans=(ans*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return ans;
}
bool operator <(Hash a,Hash b){return(a.a<b.a || (a.a==b.a && a.b<b.b));}
Hash operator -(Hash a,Hash b){a.a=(a.a-b.a+p1)%p1;a.b=(a.b-b.b+p2)%p2;return a;}
Hash operator +(Hash a,Hash b){a.a=(a.a+b.a)%p1;a.b=(a.b+b.b)%p2;return a;}
Hash operator *(Hash a,Hash b){a.a=(a.a*b.a)%p1;a.b=(a.b*b.b)%p2;return a;}
Hash operator *(Hash a,ll b){a.a=(a.a*b)%p1;a.b=(a.b*b)%p2;return a;}
Hash operator +(Hash a,ll b){a.a=(a.a+b%p1)%p1;a.b=(a.b+b%p2)%p2;return a;}
Hash operator -(Hash a,ll b){a.a=(a.a-b%p1+p1)%p1;a.b=(a.b-b%p2+p2)%p2;return a;}
Hash operator /(Hash a,Hash b)
{
	a.a=(a.a*m_pow(b.a,p1-2,p1))%p1;
	a.b=(a.b*m_pow(b.b,p2-2,p2))%p2;
	return a;
}
signed main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	pos=250000;l=inf;r=0;
	for (int i=1;i<=n;i++)
	{
		l=min(l,pos);r=max(r,pos);
		if (s[i]=='+') a[pos]++;
		if (s[i]=='-') a[pos]--;
		if (s[i]=='>') pos++;
		if (s[i]=='<') pos--;
	}
	z[0].a=1;z[0].b=1;
	for (int i=1;i<=r;i++) z[i]=z[i-1]*base;
	pos=250000;
//	for (int i=l;i<=r;i++) add=add+z[i]*delta;
//	for (int i=l;i<=r;i++) h[0]=h[0]+z[i]*delta;
	for (int i=1;i<=n;i++)
	{
		h[i]=h[i-1];
		if (s[i]=='+') h[i]=h[i]+z[pos];
		if (s[i]=='-') h[i]=h[i]-z[pos];
		if (s[i]=='>') pos++;
		if (s[i]=='<') pos--;
	}
	now=h[n];h[0].a=h[0].b=0;
	for (int i=1;i<=n;i++) mp[h[i]]++;
	pos=250000;
	for (int i=1;i<=n;i++)
	{
//		(now*z[pos-250000]+h[0]).print();
		if (pos>250000) ans+=mp[now*z[pos-250000]+h[0]];
		else ans+=mp[now/z[250000-pos]+h[0]];
		mp[h[i]]--;
		if (s[i]=='+') h[0]=h[0]+z[pos];
		if (s[i]=='-') h[0]=h[0]-z[pos];
		if (s[i]=='>') pos++;
		if (s[i]=='<') pos--;
	}
	printf("%lld\n",ans);
}