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<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int mod=998244353;
int sed[6]={3,233,23,19260817,97,101};
int vsed[6];
struct data
{
	int a[6];
	friend bool operator < (data a,data b)
	{
		for(int i=0;i<6;++i)if(a.a[i]!=b.a[i])return a.a[i]<b.a[i];
		return 0;
	}
};
inline int kpow(int a,int b)
{
	int s=1;
	for(;b;b>>=1,a=1ll*a*a%mod)
		if(b&1)s=1ll*s*a%mod;
	return s;
}
long long ans;
int n,c[6],d[6];
char s[250050];
pair<int,int>s1[6];
map<data,int>mp;
void work(char cur)
{
	for(int i=0;i<6;++i)
	{
		if(cur=='>')s1[i].first=1ll*s1[i].first*vsed[i]%mod;
		else if(cur=='<')s1[i].first=1ll*s1[i].first*sed[i]%mod;
		else if(cur=='+')(s1[i].second+=s1[i].first)%=mod;
		else (s1[i].second+=mod-s1[i].first)%=mod;	
	}
}
data get(int x[6])
{
	static data now;
	for(int i=0;i<6;++i)now.a[i]=(1ll*x[i]*s1[i].first+s1[i].second)%mod;
	return now;
}
int main()
{
	for(int i=0;i<6;++i)vsed[i]=kpow(sed[i],mod-2);
	scanf("%d %s",&n,s+1);
	for(int i=n;i;--i)
		for(int j=0;j<6;++j)
		{
			if(s[i]=='>')c[j]=1ll*c[j]*vsed[j]%mod;
			else if(s[i]=='<')c[j]=1ll*c[j]*sed[j]%mod;
			else if(s[i]=='+')(c[j]+=1)%=mod;
			else (c[j]+=mod-1)%=mod;			
		}
	for(int j=0;j<6;++j)s1[j].first=1;
	++mp[get(c)];
	for(int i=1;i<=n;++i)
	{
		work(s[i]);
		ans+=mp[get(d)];
		++mp[get(c)];
	}
	printf("%lld",ans);
	return 0;
}