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 dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
#define dbg3(x) cerr<<#x<<"\n"
using namespace std;
#define reg register
const int MN=250005;
int N;
char s[MN];
const int P=998244353;
int Add(int x,int y){return (x+y)%P;}
int Mul(int x,int y){return (1ll*x*y)%P;}
const int B[]={691,769,823,877,911,967},
inv[]={37560569,983965175,992179685,349442436,115055606,356147158};
struct node
{
	int v[6];
	int& operator [](int x){return v[x];}
	bool operator <(const node o)const
	{
		for(int i=0;i<6;++i)if(v[i]!=o.v[i])return v[i]<o.v[i];
		return false;
	}
	bool operator ==(const node o)const
	{
		for(int i=0;i<6;++i)if(v[i]!=o.v[i])return false;
		return true;
	}
}pre[MN],all;
std::map<node,int> Mp;
int pos[MN],nm[6][MN<<1],cal[MN];
node get(node x,node y,int p)
{
	for(int j=0;j<6;++j)
		x[j]=Add(x[j],Mul(y[j],nm[j][p]));
	return x;
}
int main()
{
	scanf("%d%s",&N,s+1);
	reg int i,j,k;
	for(j=0;j<6;++j)for(nm[j][MN]=i=1;i<=N;++i)
		nm[j][i+MN]=Mul(nm[j][i-1+MN],B[j]),
		nm[j][-i+MN]=Mul(nm[j][-i+1+MN],inv[j]);
	for(k=j=0;j<6;++j,k=0)for(i=1;i<=N;++i)
	{
		switch(s[i])
		{
			case '<':--k;break;
			case '>':++k;break;
			case '+':all[j]=Add(all[j],nm[j][k+MN]);break;
			case '-':all[j]=Add(all[j],P-nm[j][k+MN]);break;
		}
		pos[i]=k;pre[i][j]=all[j];
	}
	++Mp[all];
	for(i=1;i<=N;++i)
		cal[i]=Mp[pre[i]],
		++Mp[get(pre[i],all,pos[i]+MN)];
	ll ans=0;
	for(i=1;i<=N;++i) ans+=cal[i];
	return 0*printf("%lld\n",ans);
}