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>

const int N = 500005;
const int base1 = 12345678, ibase1 = 749734780, mod1 = 998244353;
const int base2 = 90123456, ibase2 = 314509124, mod2 = 1000000007;
typedef long long LL;
typedef std::pair<int, int> hashing;
#define x first
#define y second

const hashing base(base1, base2);
const hashing ibase(ibase1, ibase2);

int add(int x, int y, int mod) { x += y - mod; return x + (x >> 31 & mod); }
int minus(int x, int y, int mod) { x -= y; return x + (x >> 31 & mod); }

hashing operator * (const hashing &lhs, const hashing &rhs) {
	return {(LL) lhs.x * rhs.x % mod1, (LL) lhs.y * rhs.y % mod2};
}
hashing operator + (const hashing &lhs, const hashing &rhs) {
	return {add(lhs.x, rhs.x, mod1), add(lhs.y, rhs.y, mod2)};
}
hashing operator - (const hashing &lhs, const hashing &rhs) {
	return {minus(lhs.x, rhs.x, mod1), minus(lhs.y, rhs.y, mod2)};
}
hashing rshift(hashing h) { return h * base; }
hashing lshift(hashing h) { return h * ibase; }

hashing pow_[N], *power = pow_ + 250000, target, backup, prefix[N];
std::map<hashing, int> map;

int n;
std::string s;
LL ans = 0;

typedef std::pair<int, hashing> tag; // X <- base^x * X + y

tag inv(tag t) { return {-t.x, hashing(0, 0) - power[-t.x] * t.y}; }
hashing apply(tag t, hashing h) { return h * power[t.x] + t.y; }

tag alltag;

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n >> s, power[0] = hashing(1, 1);
	for (int i = 1; i <= n; ++i) power[i] = power[i - 1] * base;
	for (int i = 1; i <= n; ++i) power[-i] = power[1 - i] * ibase;
	for (int i = 0, p = 0; i < n; ++i) {
		if (s[i] & 1)
			target = s[i] == 43 ? target + power[p] : target - power[p];
		else
			p += s[i] == 60 ? -1 : 1;
	}
	for (int i = n - 1; ~i; --i) {
		++map[apply(inv(alltag), hashing(0, 0))];
		if (s[i] & 1) alltag.y = alltag.y + (s[i] == 43 ? hashing(1, 1) : hashing(mod1 - 1, mod2 - 1));
		else alltag.y = alltag.y * (s[i] == 60 ? ibase : base), alltag.x += s[i] == 60 ? -1 : 1;
		ans += map[apply(inv(alltag), target)];
	}
	std::cout << ans << '\n';
	return 0;
}