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
#define uLL unsigned long long
#define db double

using namespace std;
const int N=250000+10;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
int fpow(int a,int b,int mod){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;}return an;}
int ginv(int a,int mod){return fpow(a,mod-2,mod);}
struct node
{
	LL x,y,z;
	bool operator < (const node &bb) const {return x!=bb.x?x<bb.x:(y!=bb.y?y<bb.y:z<bb.z);}
	bool operator == (const node &bb) const {return x==bb.x&&y==bb.y&&z==bb.z;}
};
map<node,int> mp;
int m1=998244853,b1=233,iv1=ginv(b1,m1),m2=1e9+7,b2=677,iv2=ginv(b2,m2),m3=993244853,b3=149,iv3=ginv(b3,m3);
char cc[N];
int n,a,b,c;

int main()
{
	n=rd();
	scanf("%s",cc+1);
	a=b=c=0;
	for(int i=n;i;--i)
	{
		if(cc[i]=='+') a=(a+1)%m1,b=(b+1)%m2,c=(c+1)%m3;
		else if(cc[i]=='-') a=(a-1+m1)%m1,b=(b-1+m2)%m2,c=(c-1+m3)%m3;
		else if(cc[i]=='<') a=1ll*a*b1%m1,b=1ll*b*b2%m2,c=1ll*c*b3%m3;
		else if(cc[i]=='>') a=1ll*a*iv1%m1,b=1ll*b*iv2%m2,c=1ll*c*iv3%m3;
	}
	int na=0,nb=0,nc=0;
	int xa=1,xb=1,xc=1;
	LL ans=0;
	mp[(node){1ll*na*xa%m1,1ll*nb*xb%m2,1ll*nc*xc%m3}]=1;
	for(int i=n;i;--i)
	{
		if(cc[i]=='+') na=(na+1)%m1,nb=(nb+1)%m2,nc=(nc+1)%m3;
		else if(cc[i]=='-') na=(na-1+m1)%m1,nb=(nb-1+m2)%m2,nc=(nc-1+m3)%m3;
		else if(cc[i]=='<')
		{
			na=1ll*na*b1%m1,nb=1ll*nb*b2%m2,nc=1ll*nc*b3%m3;
			xa=1ll*xa*iv1%m1,xb=1ll*xb*iv2%m2,xc=1ll*xc*iv3%m3;
		}
		else if(cc[i]=='>')
		{
			na=1ll*na*iv1%m1,nb=1ll*nb*iv2%m2,nc=1ll*nc*iv3%m3;
			xa=1ll*xa*b1%m1,xb=1ll*xb*b2%m2,xc=1ll*xc*b3%m3;
		}
		ans+=mp[(node){1ll*(na-a+m1)*xa%m1,1ll*(nb-b+m2)*xb%m2,1ll*(nc-c+m3)*xc%m3}];
		++mp[(node){1ll*na*xa%m1,1ll*nb*xb%m2,1ll*nc*xc%m3}];
	}
	printf("%lld\n",ans);
    return 0;
}