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:
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 500005
#define inf 1e9
#define eps 1e-10
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

map <ull,int> p;
ull b[maxn],inv[maxn],ans;
int len,n;
char s[maxn];

inline ull pw(ull a,ull b)
{
	ull ans=1,base=a;
	while(b)
	{
		if(b&1) ans=(ans*base);
		base=(base*base); b>>=1;
	}
	return ans;
}

int main()
{
	//freopen("t1.out","w",stdout);
	ull x=0-1; ull y=pw(233,x-1); //cout<<x*y<<endl;
	n=read(); scanf("%s",s+1); b[0]=1; inv[0]=1; inv[1]=7204522363551799129; len=strlen(s+1);
	for(int i=1;i<=maxn-5;i++) b[i]=b[i-1]*233;
	for(int i=2;i<=maxn-5;i++) inv[i]=inv[i-1]*7204522363551799129;
	ll ed=0,nw=250000;
	for(int i=1;i<=len;i++)
	{
		if(s[i]=='+') ed=(ed+b[nw]);
		else if(s[i]=='-') ed=(ed-b[nw]);
		else if(s[i]=='>') nw++;
		else if(s[i]=='<') nw--; p[ed]++;
	}
	ll tmp=0; nw=250000; ans=0;
	for(int i=1;i<=len;i++)
	{
		ll p2=ed;
		if(nw>=250000) p2=(p2*b[nw-250000]);
		else p2=(p2*inv[250000-nw]);
		ans+=p[(tmp+p2)];
		if(s[i]=='+') tmp=(tmp+b[nw]);
		else if(s[i]=='-') tmp=(tmp-b[nw]);
		else if(s[i]=='>') nw++;
		else if(s[i]=='<') nw--;
		p[tmp]--;
	}
	cout<<ans<<endl;
	return 0;
}