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> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

LL inv(LL a , LL p){
	LL ret = 1;
	for(LL i = p-2 ; i ; i /= 2){
		if(i&1) (ret *= a) %= p;
		a = a * a % p;
	}
	return ret;
}

const int RH_prime = 3;
const LL RH_mod[] = {1000000007,1000000021,1000000033};
const LL base = 314159;

struct RH{
	int n;
	vector<LL> hash[RH_prime];
	vector<LL> pw[RH_prime];
	
	RH(){n=0;}
	RH(const string &s){
		n = (int)s.size();
		for(int i = 0 ; i < RH_prime ; ++i){
			hash[i].push_back(0);
			pw[i].push_back(1);
			for(int j = 0 ; j < n ; ++j){
				if(s[j] == '+' || s[j] == '-'){
					hash[i].push_back((hash[i][j] + (s[j]=='-'?RH_mod[i]-pw[i][j]:pw[i][j])) % RH_mod[i]);
					pw[i].push_back(pw[i][j]);
				} else {
					hash[i].push_back(hash[i][j]);
					pw[i].push_back(pw[i][j] * (s[j]=='>'?base:inv(base,RH_mod[i])) % RH_mod[i]);
				}
			}
		}
	}
};

int main(){
	int N; cin >> N;
	string S; cin >> S;
	RH rh(S);
	map<tuple<LL,LL,LL>,int> M;
	LL ans = 0;
	repm(i,N,0){
		++M[make_tuple(rh.hash[0][i],rh.hash[1][i],rh.hash[2][i])];
		tuple<LL,LL,LL> z = make_tuple((rh.hash[0][N]*rh.pw[0][i-1]+rh.hash[0][i-1])%RH_mod[0],
							 (rh.hash[1][N]*rh.pw[1][i-1]+rh.hash[1][i-1])%RH_mod[1],
							 (rh.hash[2][N]*rh.pw[2][i-1]+rh.hash[2][i-1])%RH_mod[2]);
		ans += M[z];
	}
	cout << ans << endl;
	return 0;
}