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<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
#define ll long long
#define inf 0x3f3f3f3f
#define mod 998244353
#define maxn 300010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static char buf[20];
	int len=0;
	if(x<0)putchar('-'),x=-x;
	for(;x;x/=10)buf[len++]=x%10+'0';
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]);
}
inline void writesp(ll x){write(x); putchar(' ');}
inline void writeln(ll x){write(x); putchar('\n');}
struct Data{
	ll k,b;
	friend Data operator * (Data a,Data b){return (Data){a.k*b.k%mod,(a.k*b.b+a.b)%mod};}
	friend int operator * (Data a,int b){return (a.k*b+a.b)%mod;}
}a1[maxn],pre1[maxn],a2[maxn],pre2[maxn];
char s[maxn];
int n,m;
ll power(ll a,ll b)
{
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)ans=ans*a%mod;
	return ans;
}
const ll base1=233,inv1=power(base1,mod-2),base2=666,inv2=power(base2,mod-2);
std::map<std::pair<int,int>,int>cnt;
int main()
{
	n=read();
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
		if(s[i]=='<')a1[i]=(Data){inv1,0},a2[i]=(Data){inv2,0};
		else if(s[i]=='>')a1[i]=(Data){base1,0},a2[i]=(Data){base2,0};
		else if(s[i]=='+')a1[i]=a2[i]=(Data){1,1};
		else a1[i]=a2[i]=(Data){1,mod-1};
	ll val1=0,val2=0;
	for(int i=n;i;i--){
		val1=a1[i]*val1;
		val2=a2[i]*val2;
	}
	pre1[0]=pre2[0]=(Data){1,0};
	for(int i=1;i<=n;i++){
		pre1[i]=pre1[i-1]*a1[i];
		pre2[i]=pre2[i-1]*a2[i];
	}
	ll ans=0;
	++cnt[std::make_pair(val1,val2)];
	for(int i=1;i<=n;i++){
		ll goal1=pre1[i].b,cur1=pre1[i]*val1,goal2=pre2[i].b,cur2=pre2[i]*val2;
		if(cnt.count(std::make_pair(goal1,goal2)))ans+=cnt[std::make_pair(goal1,goal2)];
		++cnt[std::make_pair(cur1,cur2)];
	}
	writeln(ans);
	return 0;
}