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 PII pair<int, int>
#define PLL pair<LL, LL>
#define f first
#define s second 
using namespace std;
const int MAXN = 250005;
const LL M1 = 1000000009;
const LL M2 = 1000000007;

LL qpow(LL a, LL pw, LL mod) {
	LL res = 1;
	while (pw) {
		if (pw & 1) res = res * a % mod;
		pw >>= 1;
		a = a * a % mod;
	}
	return res;
}

PLL norm(PLL p) {
	return PLL((p.f % M1 + M1) % M1, (p.s % M2 + M2) % M2);
}

PLL neg(PLL p) {
	return PLL(M1 - p.f, M2 - p.s);
}

PLL get_inv(PLL p) {
	return PLL(qpow(p.f, M1 - 2, M1), qpow(p.s, M2 - 2, M2));
}

PLL mul(PLL p, PLL q) {
	return PLL(p.f * q.f % M1, p.s * q.s % M2);
}

PLL add(PLL p, PLL q) {
	return PLL((p.f + q.f) % M1, (p.s + q.s) % M2);
}

int n;
string s;
PLL pw[2*MAXN], pinv[2*MAXN], pref[MAXN];
LL pos[MAXN];

int main() { 
	ios_base::sync_with_stdio(0); cin.tie(0);

	PLL base = PLL(1234567, 7654321), inv = get_inv(base);
	pw[0] = pinv[0] = {1, 1};
	for (int i = 1; i < 2 * MAXN; i++) {
		pw[i] = mul(pw[i - 1], base);
		pinv[i] = mul(pinv[i - 1], inv);
	}

	cin >> n >> s;
	pref[0] = PLL(0, 0);
	pos[0] = n;
	map<PLL, int> cnt;
	for (int i = 1; i <= n; i++) {
		char t = s[i - 1];
		pos[i] = pos[i - 1];
		pref[i] = pref[i - 1];
		if (t == '<') pos[i]--;
		if (t == '>') pos[i]++;
		if (t == '+') pref[i] = add(pref[i], pw[pos[i]]);
		if (t == '-') pref[i] = add(pref[i], neg(pw[pos[i]]));
		cnt[pref[i]]++;
	}
	
	LL ans = 0; 
	PLL tgt = pref[n], mulf = PLL(1, 1), addf = PLL(0, 0);
	for (int i = 1; i <= n; i++) {
		ans += cnt[add(mul(get_inv(mulf), tgt), neg(mul(get_inv(mulf), addf)))];
//		cout << "At " << i << ' ' << cnt[add(mul(tgt, mulf), addf)] << '\n';
		
		char t = s[i - 1];
		cnt[pref[i]]--;
		if (t == '<') {
			// a *= base, b *= base
			mulf = mul(mulf, pw[1]);
			addf = mul(addf, pw[1]);
		}
		if (t == '>') {
			// a /= base, b /= base
			mulf = mul(mulf, pinv[1]);
			addf = mul(addf, pinv[1]);
		}
		if (t == '+') {
			// b -= pw[n]
			addf = add(addf, neg(pw[n]));
		}
		if (t == '-') {
			// b += pw[n]
			addf = add(addf, pw[n]);
		}
	}
	
	cout << ans << '\n';

	return 0;
}