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:
//#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;

#define boost ios::sync_with_stdio(0); cin.tie(0)

#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int, int> pii;

const int X = 250000 + 5;
const int N = 1e6 + 5;
const ull B = 545;
ull invB;

/***************************************************************************/

ull power(ull a, ull n) {
	if(n == 0) return 1;
	ull p = power(a, n>>1);
	p = p * p;
	if(n & 1) p = p * a;
	return p;
}

string S;
ull powB[N];

inline ull& pow(int n) {
	if(n < 0) n += N;
	return powB[n];
}

map<ull, int> M;

int main() {

	boost;
	invB = power(B, (ull(1)<<63)-1);
	assert(B * invB == 1);

	pow(0) = 1;
	for(int i=1; i<X; i++) {
		pow(i) = pow(i-1) * B;
		pow(-i) = pow(-i+1) * invB;
	}

	int n; cin>>n;
	cin>>S;

	ull phas = 0, chas = 0;

	int p = 0;
	for(auto it : S) {
		if(it == '+') phas += pow(p);
		else if(it == '-') phas -= pow(p);
		else if(it == '>') p++;
		else p--;
	}

	ll ans = 0;
	M[phas]++;
	p = 0;

	for(auto it : S) {
		if(it == '+') chas += pow(p);
		else if(it == '-') chas -= pow(p);
		else if(it == '>') p++;
		else p--;

		ans += M[chas];
		M[chas + pow(p) * phas]++;
	}

	cout<<ans<<"\n";

	return 0;
}