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 fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const ll mo = 23333333333333333;

ll mul(ll x, ll y) {
	x %= mo, y %= mo;
	ll z = (long double) x * y / mo;
	z = x * y - z * mo;
	if(z < 0) z += mo; else if(z >= mo) z -= mo;
	return z;
}

ll ksm(ll x, ll y) {
	ll s = 1;
	for(; y; y /= 2, x = mul(x, x))
		if(y & 1) s = mul(s, x);
	return s;
}

const ll w = 1e9 + 7;

const int N = 250005;

ll aw[N * 2], v[N * 2];
int n; char s[N];

map<ll, int> cnt;

ll ans;

int main() {
	scanf("%d", &n);
	scanf("%s", s + 1);
	aw[0] = 1; fo(i, 1, n * 2) aw[i] = mul(aw[i - 1], w);
	v[0] = ksm(ksm(w, mo - 2), n); fo(i, 1, n * 2) v[i] = mul(v[i - 1], w);
	ll p = n, sum = 0;
	fo(i, 1, n) {
		if(s[i] == '<') {
			p --;
		}
		if(s[i] == '>') {
			p ++;
		}
		if(s[i] == '+') {
			sum = (sum + aw[p]) % mo;
		}
		if(s[i] == '-') {
			sum = (sum - aw[p] + mo) % mo;
		}
	}
	ll eds = sum;
	p = n, sum = 0;
	cnt[(mul(eds, v[p]) + sum) % mo] ++;
	fo(i, 1, n) {
		if(s[i] == '<') {
			p --;
		}
		if(s[i] == '>') {
			p ++;
		}
		if(s[i] == '+') {
			sum = (sum + aw[p]) % mo;
		}
		if(s[i] == '-') {
			sum = (sum - aw[p] + mo) % mo;
		}
		ans += cnt[sum];
		cnt[(mul(eds, v[p]) + sum) % mo] ++;
	}
	pp("%lld\n", ans);

}