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;

const int mod=1012200221;
int ran(){return rand()%1000*1000000+rand()%1000*1000+rand()%1000+1;}

long long ans;
int n,v[9],inv[9];
char s[250010];
struct node{int nw[9];}c,fk[250010],fb[250010],O;

bool operator <(node a,node b)
{
	for (int i=0; i<9; i++)
	{
		if (a.nw[i]<b.nw[i]) return 1;
		if (a.nw[i]>b.nw[i]) return 0;
	}
	return 0;
}

map<node,int> ma;

node f1(node x) 
{
	for (int i=0; i<9; i++) x.nw[i]=(x.nw[i]==mod-1?0:x.nw[i]+1);
	return x;
}

node f2(node x)
{
	for (int i=0; i<9; i++) x.nw[i]=(x.nw[i]==0?mod-1:x.nw[i]-1);
	return x;
}

node f3(node x)
{
	for (int i=0; i<9; i++) x.nw[i]=1ll*x.nw[i]*v[i]%mod;
	return x;
}

node f4(node x)
{
	for (int i=0; i<9; i++) x.nw[i]=1ll*x.nw[i]*inv[i]%mod;
	return x;
}

node operator +(node a,node b)
{
	for (int i=0; i<9; i++) a.nw[i]=(a.nw[i]+b.nw[i]>=mod?a.nw[i]+b.nw[i]-mod:a.nw[i]+b.nw[i]);
	return a;
}

node operator -(node a,node b)
{
	for (int i=0; i<9; i++) a.nw[i]=(a.nw[i]<b.nw[i]?a.nw[i]-b.nw[i]+mod:a.nw[i]-b.nw[i]);
	return a;
}

node operator *(node a,node b)
{
	for (int i=0; i<9; i++) a.nw[i]=1ll*a.nw[i]*b.nw[i]%mod;
	return a;
}

int quickmi(int a,int b)
{
	int t=1;
	for (; b; b>>=1,a=1ll*a*a%mod)
		if (b&1) t=1ll*t*a%mod;
	return t;
}

int main()
{
	srand(114514),O=(node){{0,0,0,0,0,0,0,0,0}};
	for (int i=0; i<9; i++) v[i]=ran(),inv[i]=quickmi(v[i],mod-2);
	scanf("%d%s",&n,s+1),c=O;
	for (int i=n; i; i--)
		if (s[i]=='+') c=f1(c); else
		if (s[i]=='-') c=f2(c); else
		if (s[i]=='>') c=f3(c); else
		if (s[i]=='<') c=f4(c);
	fk[n+1]=f1(O),fb[n+1]=O;
	for (int i=n; i; i--)
		if (s[i]=='+') fb[i]=(fb[i+1]-fk[i+1]),fk[i]=fk[i+1]; else
		if (s[i]=='-') fb[i]=(fb[i+1]+fk[i+1]),fk[i]=fk[i+1]; else
		if (s[i]=='>') fb[i]=fb[i+1],fk[i]=f4(fk[i+1]); else
		if (s[i]=='<') fb[i]=fb[i+1],fk[i]=f3(fk[i+1]);
	ma.clear(),ans=0;
	for (int i=n; i; i--)
	{
		ma[fb[i+1]]++;
		ans+=ma[(fk[i]*c)+fb[i]];
	}
	return printf("%lld\n",ans),0;
}