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;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int maxn=(2.5e5)+10;
const ll mod=(1e9)+7;
const ll t1=998244353;
const ll t2=235723657;
int n,pos[maxn];
char s[maxn];
ll h1[maxn],h2[maxn];
ll m1[maxn*2],m2[maxn*2],a[maxn*2],ans,s1,s2;
ll iv1[maxn*2],iv2[maxn*2];
map<pair<ll,ll> ,int> M;
ll MI1(int x) {
	if (x>=0) return m1[x];
	return iv1[-x];
}
ll MI2(int x) {
	if (x>=0) return m2[x];
	return iv2[-x];
}
ll get1(int x) {
	return a[x+n]*MI1(x)%mod;
}
ll get2(int x) {
	return a[x+n]*MI2(x)%mod;
}
ll ksm(ll x,ll y) {
	ll res=1;
	while (y) {
		if (y&1) res=res*x%mod;
		x=x*x%mod; y>>=1;
	} return res;
}
void F(ll &x) {
	x=(x%mod+mod)%mod;
}
int main() {
	//freopen("1.txt","r",stdin);
	read(n);
	scanf("%s",s+1);
	m1[0]=m2[0]=1;
	for (int i=1;i<=n*2;i++) m1[i]=m1[i-1]*t1%mod,m2[i]=m2[i-1]*t2%mod;
	iv1[0]=iv2[0]=1;
	iv1[1]=ksm(t1,mod-2);
	iv2[1]=ksm(t2,mod-2);
	for (int i=2;i<=n*2;i++)
		iv1[i]=iv1[i-1]*iv1[1]%mod,
		iv2[i]=iv2[i-1]*iv2[1]%mod;
	for (int i=1;i<=n;i++) {
		h1[i]=h1[i-1]; h2[i]=h2[i-1]; pos[i]=pos[i-1];
		if (s[i]=='+') {
			h1[i]-=get1(pos[i]);
			h2[i]-=get2(pos[i]);
			a[pos[i]+n]++;
			h1[i]+=get1(pos[i]);
			h2[i]+=get2(pos[i]);
		} else if (s[i]=='-') {
			h1[i]-=get1(pos[i]);
			h2[i]-=get2(pos[i]);
			a[pos[i]+n]--;
			h1[i]+=get1(pos[i]);
			h2[i]+=get2(pos[i]);
		} else if (s[i]=='>') pos[i]++;
		else pos[i]--;
		F(h1[i]);
		F(h2[i]);
	}
	for (int i=n-1;i>=0;i--) {
		M[make_pair(h1[i+1],h2[i+1])]++;
		s1=h1[n]*MI1(pos[i])%mod+h1[i];
		s2=h2[n]*MI2(pos[i])%mod+h2[i];
		F(s1); F(s2);
		ans+=M[make_pair(s1,s2)];
	}
	printf("%lld\n",ans);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Interger overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/