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<algorithm>
#include<map>
using namespace std;
const int MAXN=250005,MOD1=1000000007,MOD2=1000000009,BASE=10007,INV1=820925358,INV2=74148097;

int PowMod(int a,int b,int P)
{
	int ret=1;
	while(b)
	{
		if(b&1)
			ret=(1LL*ret*a)%P;
		b>>=1;
		a=(1LL*a*a)%P;
	}
	return ret;
}

struct Hash
{
	int a,b;
	Hash(){}
	Hash(int a,int b):a(a),b(b){}
	Hash operator + (Hash y)
	{return Hash((a+y.a)%MOD1,(b+y.b)%MOD2);}
	Hash operator - (Hash y)
	{return Hash((a-y.a+MOD1)%MOD1,(b-y.b+MOD2)%MOD2);}
	Hash operator * (Hash y)
	{return Hash((1LL*a*y.a)%MOD1,(1LL*b*y.b)%MOD2);}
	bool operator < (Hash y)const
	{return a<y.a||(a==y.a&&b<y.b);}
};

int N;
char S[MAXN];
Hash P[MAXN],op[MAXN];

map<Hash,int> cnt;

int main()
{
	//printf("%d\n",PowMod(BASE,MOD1-2,MOD1));
	//printf("%d\n",PowMod(BASE,MOD2-2,MOD2));
	scanf("%d%s",&N,S+1);
	P[0]=Hash(1,1);
	for(int i=1;i<=N;i++)
	{
		P[i]=P[i-1];op[i]=op[i-1];
		if(S[i]=='<')
			P[i]=P[i]*Hash(INV1,INV2);
		if(S[i]=='>')
			P[i]=P[i]*Hash(BASE,BASE);
		if(S[i]=='+')
			op[i]=op[i]+P[i];
		if(S[i]=='-')
			op[i]=op[i]-P[i];
	}
	
	long long ans=0;
	for(int i=N;i>=1;i--)
	{
		cnt[op[i]]++;
		ans+=cnt[op[N]*P[i-1]+op[i-1]];
	}
	
	printf("%lld\n",ans);
	
	return 0;
}