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
using namespace std;
const int B=131,P[2]={998244353,1000000007},MAXN=250010;
int n,nw[MAXN],nt[2],INV[2];
int hs[2][MAXN];
ll ans;
char s[MAXN];
map <int,int> mp[2];
int qpow (int a,int b,int p) {
	if (b<0) {a=qpow(a,p-2,p),b=-b;}
	int res=1;
	while (b) {
		if (b&1) {res=(1ll*res*a)%p;}
		a=(1ll*a*a)%p,b>>=1;
	}
	return res;
}
int main () {
	INV[0]=qpow(B,P[0]-2,P[0]),INV[1]=qpow(B,P[1]-2,P[1]);
	nt[0]=qpow(B,n,P[0]),nt[1]=qpow(B,n,P[1]);
	scanf("%d%s",&n,s+1);
	nw[0]=0;
	mp[0][0]++,mp[1][0]++;
	for (int i=1;i<=n;i++) {
		if (s[i]=='+') {
			hs[0][i]=(hs[0][i-1]+nt[0])%P[0];
			hs[1][i]=(hs[1][i-1]+nt[1])%P[1];
			nw[i]=nw[i-1];
		} else if (s[i]=='-') {
			hs[0][i]=(hs[0][i-1]-nt[0]+P[0])%P[0];
			hs[1][i]=(hs[1][i-1]-nt[1]+P[1])%P[1];
			nw[i]=nw[i-1];
		} else if (s[i]=='<') {
			nt[0]=(1ll*nt[0]*INV[0])%P[0];
			nt[1]=(1ll*nt[1]*INV[1])%P[1];
			hs[0][i]=hs[0][i-1],hs[1][i]=hs[1][i-1],nw[i]=nw[i-1]+1;
		} else {
			nt[0]=(1ll*nt[0]*B)%P[0];
			nt[1]=(1ll*nt[1]*B)%P[1];
			hs[0][i]=hs[0][i-1],hs[1][i]=hs[1][i-1],nw[i]=nw[i-1]-1;
		}
		mp[0][hs[0][i]]++,mp[1][hs[1][i]]++;
		//cout << i << "  " << hs[0][i] << "  " << hs[1][i] << "  " << nw[i] << endl;
	}
	for (int i=0;i<=n-1;i++) {
		mp[0][hs[0][i]]--,mp[1][hs[1][i]]--;
		int tmp0=(1ll*(hs[0][n]+(1ll*hs[0][i]*qpow(B,nw[i],P[0]))%P[0])*qpow(INV[0],nw[i],P[0]))%P[0];
		int tmp1=(1ll*(hs[1][n]+(1ll*hs[1][i]*qpow(B,nw[i],P[1]))%P[1])*qpow(INV[1],nw[i],P[1]))%P[1];
		//cout << i << "  " << tmp0 << "  " << tmp1 << endl;
		if (mp[0].find(tmp0)==mp[0].end()||mp[1].find(tmp1)==mp[1].end()) {continue;}
		ans+=min(mp[0][tmp0],mp[1][tmp1]);
	}
	printf("%lld\n",ans);
	return 0;
}