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 ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int N=250005;
const int mo=998244353;
const int p[]={233,2333,23333,233333,2333333};
int P[5][N*2];
int posi[N];
struct node{
	int a[5];
	bool operator <(const node &b)const{
		For(i,0,4)
			if (a[i]!=b.a[i])
				return a[i]<b.a[i];
		return 0;
	}
	bool operator ==(const node &b)const{
		For(i,0,4)
			if (a[i]!=b.a[i])
				return 0;
		return 1;
	}
}a[N];
int n;
ll ans;
char s[N];
map<node,int> mp;
int power(int x,int y){
	int s=1;
	for (;y;y/=2,x=1ll*x*x%mo)
		if (y&1) s=1ll*s*x%mo;
	return s;
}
int main(){
	scanf("%d%s",&n,s+1);
	For(i,0,4) P[i][0]=1;
	For(i,1,N*2-1) For(j,0,4)
		P[j][i]=1ll*P[j][i-1]*p[j]%mo;
	int pos=N; posi[0]=N;
	For(i,1,n){
		a[i]=a[i-1];
		if (s[i]=='+')
			For(j,0,4)
				a[i].a[j]=(a[i].a[j]+P[j][pos])%mo;
		if (s[i]=='-')
			For(j,0,4)
				a[i].a[j]=(a[i].a[j]+mo-P[j][pos])%mo;
		if (s[i]=='<') --pos;
		if (s[i]=='>') ++pos;
		posi[i]=pos;
	}
	For(i,0,n) mp[a[i]]++;
	For(i,0,n-1){
		node tmp=a[n]; mp[a[i]]--;
		For(j,0,4) tmp.a[j]=1ll*tmp.a[j]*power(p[j],mo-1+posi[i]-posi[0])%mo;
		For(j,0,4) tmp.a[j]=(tmp.a[j]+a[i].a[j])%mo;
		ans+=mp[tmp];
	}
	printf("%lld\n",ans);
}