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 <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define inver(a,mod) power(a,mod-2,mod)
#define idx(a,b) ((ll)(a)*mod[1]+(b))
using namespace std;
template<class T> void rd(T &x) {
	x=0; int f=1,ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=getchar();}
	x*=f;
}
typedef long long ll;
const int mod[2]={998244353,1004535809};
const int maxn=250000+50;
int bs[2],rb[2];
int n; char s[maxn];
int c[2];
map<ll,int> cnt;
struct func {
	int k,b;
	func(int k=1,int b=0):k(k),b(b){}
	inline int f(int x,int mod) {
		return ((ll)k*x+b)%mod;
	}
} a[maxn][2];
inline func mer(func a,func b,int mod) {
	return func((ll)a.k*b.k%mod,((ll)a.b*b.k+b.b)%mod);
}
inline int add(int x,int mod) {return x>=mod?x-mod:x;}
inline int sub(int x,int mod) {return x<0?x+mod:x;}
ll power(ll x,ll y,int mod) {
	ll re=1;
	while(y) {
		if(y&1) re=re*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return re;
}
void init() {
	srand((unsigned long long)(new char));
	bs[0]=rand(),rb[0]=inver(bs[0],mod[0]);
	bs[1]=rand(),rb[1]=inver(bs[1],mod[1]);
}
int main() {
	init();
	rd(n);
	scanf("%s",s+1);
	for(int i=n;i>=1;--i) for(int k=0;k<2;++k) {
		func f; switch(s[i]) {
			case '+': f=func(1,mod[k]-1),c[k]=add(c[k]+1,mod[k]); break;
			case '-': f=func(1,1),c[k]=sub(c[k]-1,mod[k]); break;
			case '>': f=func(rb[k],0),c[k]=(ll)c[k]*bs[k]%mod[k]; break;
			case '<': f=func(bs[k],0),c[k]=(ll)c[k]*rb[k]%mod[k]; break;
		}
		a[i][k]=mer(f,a[i+1][k],mod[k]);
	}
	ll an=0;
	++cnt[0];
	for(int i=n;i>=1;--i) {
		an+=cnt[idx(a[i][0].f(c[0],mod[0]),a[i][1].f(c[1],mod[1]))];
		++cnt[idx(a[i][0].f(0,mod[0]),a[i][1].f(0,mod[1]))];
	}
	printf("%lld\n",an);
	return 0;
}