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>
using namespace std;
typedef long long ll;
const int N=300005,K=4,p=998244353;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int qpow(int x,int k){
	int t=1;
	for (;k;k>>=1){
		if (k&1) t=(ll)t*x%p;
		x=(ll)x*x%p;
	}
	return t;
}
struct state{
	int a[K];
	int &operator[](int i){return a[i];}
	state(){memset(a,0,sizeof(a));}
}x,rx,s[N][2],c,e;
bool operator==(state a,state b){
	for (int i=0;i<K;i++)
	if (a[i]==b[i]) return false;
	return true;
}
bool operator<(state a,state b){
	for (int i=0;i<K;i++)
	if (a[i]!=b[i]) return a[i]<b[i];
	return false;
}
state operator*(state x,state y){for (int i=0;i<K;i++) x[i]=(ll)x[i]*y[i]%p;return x;}
state operator+(state x,state y){for (int i=0;i<K;i++) if((x[i]+=y[i])>=p) x[i]-=p;return x;}
state operator-(state x,state y){for (int i=0;i<K;i++) if((x[i]-=y[i])<0) x[i]+=p;return x;}
state operator+(state x,int k){for (int i=0;i<K;i++) if ((x[i]+=k)>=p) x[i]-=p;return x;}
state operator-(state x,int k){for (int i=0;i<K;i++) if ((x[i]-=k)<0) x[i]+=p;return x;}
state getval(state *a,state x){
	state cur=a[0]+a[1]*x;
	return cur;
}
int n,m;
ll ans;
char ch[N];
map<state,int> f;
int main(){
	for (int i=0;i<K;i++) x[i]=i+1,rx[i]=qpow(x[i],p-2);
	n=read();
	scanf(" %s",ch+1);
	for (int i=0;i<K;i++) s[n+1][1][i]=1;
	for (int i=n;i;i--)
	if (ch[i]=='+'){s[i][0]=s[i+1][0]+s[i+1][1];s[i][1]=s[i+1][1];c=c-1;}
	else if (ch[i]=='-'){s[i][0]=s[i+1][0]-s[i+1][1];s[i][1]=s[i+1][1];c=c+1;}
	else if (ch[i]=='>'){s[i][0]=s[i+1][0];s[i][1]=s[i+1][1]*x;c=c*rx;}
	else if (ch[i]=='<'){s[i][0]=s[i+1][0];s[i][1]=s[i+1][1]*rx;c=c*x;}
	for (int i=n;i;i--){
		f[getval(s[i+1],e)]++;
		ans+=f[getval(s[i],c)];
	}
	printf("%lld\n",ans);
	return 0;
}