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 fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
#define get(x)((x)>=0?_A[x]:_A2[-(x)])
#define ll long long
using namespace std;
const int N=2.5e5+5;
const ll mo=23333333333333333LL;
int n;
ll Z,A,_A[N],_A2[N],Y,ans;
map<ll,int>h;
char c[N];
inline ll mult(ll x,ll y){
	Z=x*y-(ll)((long double)x*y/mo)*mo;
	return (Z<0?Z+mo:Z<mo?Z:Z-mo);
}
ll ksm(ll x,ll y){
	ll t=1;
	for(;y;y>>=1,x=mult(x,x))if(y&1)t=mult(t,x);
	return t;
}
struct P{
	int x;ll y;
	P(int _x=0,ll _y=0){x=_x;y=_y;}
	P operator+(const P &b){
		return P(x+b.x,(y+mult(get(x),b.y))%mo);
	}
}a[N];
int main(){
	scanf("%d\n%s",&n,c+1);
	A=1e6+7;
	_A[0]=1;
	fo(i,1,n)_A[i]=mult(_A[i-1],A);
	_A2[0]=1;_A2[1]=ksm(A,mo-2);
	fo(i,2,n)_A2[i]=mult(_A2[i-1],_A2[1]);
	fd(i,1,n){
		if(c[i]=='>')a[i]=P(1,0);
		if(c[i]=='<')a[i]=P(-1,0);
		if(c[i]=='+')a[i]=P(0,1);
		if(c[i]=='-')a[i]=P(0,-1);
		a[i]=a[i]+a[i+1];
	}
	Y=a[1].y;
	fd(i,1,n+1){
		ll b=mult((a[i].y-Y+mo)%mo,get(-a[i].x));
		ans+=h[b];
		b=mult(a[i].y,get(-a[i].x));
		++h[b];
	}
	cout<<ans;
}