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 mo1 1019260817
#define mo2 1009260817
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int pow(int x,int y,int mo){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mo;
		x=1ll*x*x%mo;y>>=1;
	}
	return ret;
}
char S[250010];
int bs1=19260817,ibs1=966804715,bs2=19491001,ibs2=251190511;
std::unordered_map<ll,int>M;
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n=gi();scanf("%s",S+1);
	int p1=1,p2=1,x1=0,x2=0;
	for(int i=1;i<=n;++i){
		if(S[i]=='+'||S[i]=='-'){
			if(S[i]=='+')x1=(x1+p1)%mo1,x2=(x2+p2)%mo2;
			else x1=(x1+mo1-p1)%mo1,x2=(x2+mo2-p2)%mo2;
		}else{
			if(S[i]=='<')p1=1ll*p1*bs1%mo1,p2=1ll*p2*bs2%mo2;
			else p1=1ll*p1*ibs1%mo1,p2=1ll*p2*ibs2%mo2;
		}
	}
	int X1=x1,X2=x2;x1=x2=0;ll ans=0;
	for(int i=1;i<=n;++i){
		int y1=(x1+1ll*X1*p1)%mo1,y2=(x2+1ll*X2*p2)%mo2;
		++M[(1ll*y1<<32)|y2];
		if(S[i]=='+'||S[i]=='-'){
			if(S[i]=='+')x1=(x1+p1)%mo1,x2=(x2+p2)%mo2;
			else x1=(x1+mo1-p1)%mo1,x2=(x2+mo2-p2)%mo2;
		}else{
			if(S[i]=='<')p1=1ll*p1*bs1%mo1,p2=1ll*p2*bs2%mo2;
			else p1=1ll*p1*ibs1%mo1,p2=1ll*p2*ibs2%mo2;
		}
		ans+=M[(1ll*x1<<32)|x2];
	}
	printf("%lld\n",ans);
	return 0;
}