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 MAXN = 3e5 + 5;
const int BASE = 3137;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;

int N;
char s[MAXN];
pii pref[MAXN], pot[MAXN];
map <pii, int> cnt;

void load() {
	scanf("%d%s", &N, s + 1);
}

inline int add(int x, int y, int mod) {
	x += y;
	if (x >= mod)
		x -= mod;
	else if (x < 0)
		x += mod;
	return x;
}

inline int mul(int x, int y, int mod) {
	return (ll)x * y % mod;
}

int power(int x, int y, int mod) {
	int res = 1;
	for (; y; y /= 2) {
		if (y % 2)
			res = mul(res, x, mod);
		x = mul(x, x, mod);
	}
	return res;
}

pii operator +(const pii &l, const pii &r) {
	return {add(l.first, r.first, MOD1), add(l.second, r.second, MOD2)};
}

pii operator *(const pii &l, const pii &r) {
	return {mul(l.first, r.first, MOD1), mul(l.second, r.second, MOD2)};
}

ll solve() {
	int inv1 = power(BASE, MOD1 - 2, MOD1);
	int inv2 = power(BASE, MOD2 - 2, MOD2);
	pot[0] = {1, 1};
	for (int i = 1; i <= N; i++) {
		pot[i] = pot[i - 1];
		pref[i] = pref[i - 1];
		if (s[i] == '>')
			pot[i] = pot[i] * pii(BASE, BASE);
		else if (s[i] == '<')
			pot[i] = pot[i] * pii(inv1, inv2);
		else if (s[i] == '+') 
			pref[i] = pref[i] + pot[i];
		else 
			pref[i] = pref[i] + pii(-pot[i].first, -pot[i].second);
	}
	
	ll ans = 0;
	for (int i = N; i; i--) {
		cnt[pref[i]]++;
		ans += cnt[(pref[N] * pot[i - 1]) + pref[i - 1]];
	}
	
	return ans;
}

int main() {
	load();
	printf("%lld\n", solve());
	return 0;
}