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 ungigned
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define vi vector<int>
#define vpi vector<pii >
#define IT iterator

#define PB push_back
#define MK make_pair
#define LB lower_bound
#define UB upper_bound
#define BG begin
#define ED end

#define For(i,j,k) for (int i=(j);i<=(int)k;i++)
#define Rep(i,j,k) for (int i=(j);i>=(int)k;i++)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));

#define LS3 k*2,l,mid
#define RS3 k*2+1,mid+1,r
#define LS5 k*2,l,mid,x,y
#define RS5 k*2+1,mid+1,r,x,y
#define GET pushdown(k);int mid=(l+r)/2
using namespace std;

const int BAS[5]={233,666,1234,19260817,2017};
const int mo=998244353;
const int N=250005;
struct wzp{
	int a[5];
	bool operator <(const wzp &x)const{
		For(i,0,4)
			if (a[i]!=x.a[i])
				return a[i]<x.a[i];
		return 0;
	}
	bool operator ==(const wzp &x)const{
		For(i,0,4)
			if (a[i]!=x.a[i])
				return 0;
		return 1;
	}
};
int P[5][N*2];
wzp hsh[N];
int pos[N];
long long ans;
map<wzp,int> mp;
char s[N];
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(){
	For(i,0,4){
		P[i][0]=1;
		For(j,1,2*N-1)
			P[i][j]=1ll*P[i][j-1]*BAS[i]%mo;
	}
	int beg=N,l; pos[0]=N;
	scanf("%d%s",&l,s+1);
	for (int i=1;i<=l;i++){
		hsh[i]=hsh[i-1];
		if (s[i]=='+') For(j,0,4) hsh[i].a[j]=(hsh[i].a[j]+P[j][beg])%mo;
		if (s[i]=='-') For(j,0,4) hsh[i].a[j]=(hsh[i].a[j]+mo-P[j][beg])%mo;
		if (s[i]=='<') beg--; if (s[i]=='>') beg++; pos[i]=beg;
	}
	for (int i=0;i<=l;i++)
		mp[hsh[i]]++;
	for (int i=0;i<l;i++){
		wzp rpos=hsh[l]; mp[hsh[i]]--;
		For(j,0,4) rpos.a[j]=1ll*rpos.a[j]*power(BAS[j],(mo-1)+pos[i]-pos[0])%mo;
		For(j,0,4) rpos.a[j]=(rpos.a[j]+hsh[i].a[j])%mo;
		ans+=mp[rpos];
	}
	printf("%lld\n",ans);
}