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>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
mt19937 ran(time(nullptr));
inline int get_mod(int x){
	return x<mod?x:x-mod;
}
struct Hasher{
	int v,v2,v3,v4;
	Hasher(int _v=0,int _v2=0,int _v3=0,int _v4=0):v(_v),v2(_v2),v3(_v3),v4(_v4){}
	inline Hasher operator+(const Hasher& rhs) const{
		return Hasher(get_mod(v+rhs.v),get_mod(v2+rhs.v2),get_mod(v3+rhs.v3),get_mod(v4+rhs.v4));
	}
	inline Hasher operator-(const Hasher& rhs) const{
		return Hasher(get_mod(v+mod-rhs.v),get_mod(v2+mod-rhs.v2),get_mod(v3+mod-rhs.v3),get_mod(v4+mod-rhs.v4));
	}
	inline Hasher operator*(const Hasher& rhs) const{
		return Hasher((ll)v*rhs.v%mod,(ll)v2*rhs.v2%mod,(ll)v3*rhs.v3%mod,(ll)v4*rhs.v4%mod);
	}
	inline bool operator<(const Hasher& rhs) const{
		return v!=rhs.v?v<rhs.v:(v2!=rhs.v2?v2<rhs.v2:(v3!=rhs.v3?v3<rhs.v3:v4<rhs.v4));
	}
	inline bool operator==(const Hasher& rhs) const{
		return v==rhs.v && v2==rhs.v2 && v3==rhs.v3 && v4==rhs.v4;
	}
} mul_pow[500010],inv_pow[500010],mul=Hasher(ran()%mod,ran()%mod,ran()%mod,ran()%mod),hash_v[250010];
map<Hasher,int> dic;
char str[250010];
inline Hasher qpow(Hasher base,int pw){
	Hasher res=Hasher(1,1);
	while(pw){
		if(pw&1) res=res*base;
		base=base*base;
		pw>>=1;
	}
	return res;
}
int main(){
	int n;
	scanf("%d%s",&n,str+1);
	mul_pow[0]=Hasher(1,1);
	inv_pow[0]=Hasher(1,1);
	Hasher mul_inv=qpow(mul,mod-2);
	for(int i=1;i<=2*n;i++){
		mul_pow[i]=mul_pow[i-1]*mul;
		inv_pow[i]=inv_pow[i-1]*mul_inv;
	}
	int pos=n;
	ll ans=0;
	for(int i=1;i<=n;i++){
		if(str[i]=='+'){
			hash_v[i]=hash_v[i-1]+mul_pow[pos];
		}else if(str[i]=='-'){
			hash_v[i]=hash_v[i-1]-mul_pow[pos];
		}else if(str[i]=='>'){
			pos++;
			hash_v[i]=hash_v[i-1];
		}else if(str[i]=='<'){
			pos--;
			hash_v[i]=hash_v[i-1];
		}
	}
	pos=n;
	for(int i=1;i<=n;i++){
		if(hash_v[i]==hash_v[n]) ans++;
		if(str[i]=='>') pos++;
		else if(str[i]=='<') pos--;
		ans+=dic[hash_v[i]];
		if(pos<n)
			dic[hash_v[n]*inv_pow[n-pos]+hash_v[i]]++;
		else
			dic[hash_v[n]*mul_pow[pos-n]+hash_v[i]]++;
	}
	printf("%lld\n",ans);
	return 0;
}