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 pb emplace_back
#define mr make_pair
#define base1 397063
#define base2 301501
#define mo1 19260817
#define mo2 998244353
#define N 500010
using namespace std;
struct Info{ll n1;int ne,qu;}a[N];
int n,b[20000010],num;
string s;
ll p2[N],p1[N],n1[N],n2[N],q1[N],q2[N],no[N],ans;
ll po(ll x,ll y,ll mo){ll z=1;while(y){if (y%2)z=x*z%mo;x=x*x%mo;y/=2;}return z;}
void add(int x,int z){
	for (int y=b[x];y;y=a[y].ne)if (a[y].n1==z){a[y].qu++;return ;}
	a[++num].qu=1;a[num].n1=z;a[num].ne=b[x];b[x]=num;
}
void que(int x,int z){
	for (int y=b[x];y;y=a[y].ne)if (a[y].n1==z)ans+=a[y].qu;
}
int main(){
	cin>>n;
	p2[0]=1,p1[0]=1;
	for (int i=1;i<=n*2;i++)p1[i]=p1[i-1]*base1%mo1,p2[i]=p2[i-1]*base2%mo2;
	n1[0]=po(po(base1,mo1-2,mo1),n,mo1);n2[0]=po(po(base2,mo2-2,mo2),n,mo2);
	for (int i=1;i<=n*2;i++)n1[i]=n1[i-1]*base1%mo1,n2[i]=n2[i-1]*base2%mo2;
	cin>>s;
	no[0]=n;
	for (int i=0;i<n;i++){
		q1[i+1]=q1[i];q2[i+1]=q2[i];no[i+1]=no[i];
		if (s[i]=='>')no[i+1]++;
		if (s[i]=='<')no[i+1]--;
		if (s[i]=='+')q1[i+1]=(q1[i+1]+p1[no[i]])%mo1,q2[i+1]=(q2[i+1]+p2[no[i]])%mo2;
		if (s[i]=='-')q1[i+1]=(q1[i+1]-p1[no[i]]+mo1)%mo1,q2[i+1]=(q2[i+1]-p2[no[i]]+mo2)%mo2;
	}
	for (int i=n;i>0;i--){add(q1[i],q2[i]);que((q1[i-1]+q1[n]*n1[no[i-1]])%mo1,(q2[i-1]+q2[n]*n2[no[i-1]])%mo2);}
	cout<<ans<<endl;
	return 0;
}