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 rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;

typedef long long lo;

template<typename tp> inline void read(tp &x) {
    x = 0; char c = getchar(); int f = 0;
    for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
    for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
    if (f) x = -x;
}

const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int base1 = 233;
const int base2 = 999;
const int N = 3e5 + 233;
const int DELTA = 1e7;
int n, _pos[N];
char str[N]; 

inline int power(int a, int k, int MOD) {
	if (k < 0) k += MOD - 1;
	int ans = 1;
	for (; k; k >>= 1, a = (lo) a * a % MOD)
		if (k & 1) ans = (lo) ans * a % MOD;
	return ans;
}

struct val_t {
	int w1, w2;
	val_t (int w1 = 0, int w2 = 0) : w1(w1), w2(w2) {}
	inline void Set(int x, int t) {
		x += DELTA;
		(w1 += (lo) power(base1, x, MOD1) * (MOD1 + t) % MOD1) %= MOD1;
		(w2 += (lo) power(base2, x, MOD2) * (MOD2 + t) % MOD2) %= MOD2;
	}
	val_t rot(int d) {
		val_t a = *this;
		a.w1 = (lo) a.w1 * power(base1, d, MOD1) % MOD1;
		a.w2 = (lo) a.w2 * power(base2, d, MOD2) % MOD2;
		return a;
	}
};
val_t val[N];
map <val_t, int> mp;

val_t operator + (val_t a, val_t b) {
	return val_t((a.w1 + b.w1) % MOD1, (a.w2 + b.w2) % MOD2);
}

bool operator < (val_t a, val_t b) {
	return make_pair(a.w1, a.w2) < make_pair(b.w1, b.w2);
}

int main(void) {
	read(n);
	scanf("%s", str + 1);
	int pos = 0;
	for (int i = 1; i <= n; i++) {
		val[i] = val[i - 1];
		if (str[i] == '+' || str[i] == '-')
			val[i].Set(pos, str[i] == '+' ? 1 : -1);
		else 
			pos += str[i] == '>' ? 1 : -1;
		_pos[i] = pos;
	}
	val_t S = val[n];
	lo ans = 0;
	for (int i = n; i >= 0; i--) {
		val_t to = S.rot(_pos[i]) + val[i];
		if (mp.count(to)) ans += mp[to];
		mp[val[i]]++;
	}
	cout << ans << "\n";
}