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 mod = 1004535809;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
int mul(int a, int b) { return (LL) a * b % mod; }
int fastpow(int a, int b, int res = 1) {
	for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a);
	return res;
}
std::mt19937 rd(time(0) + (size_t) new char);
const int MAXN = 250010;
struct func {
	int a, b;
	func() { a = b = 0; }
	func(int x, int y) { a = x, b = y; }
	friend func operator + (func x, func y){ // x(y())
		return func(mul(x.a, y.a), ((LL) x.a * y.b + x.b) % mod);
	}
	int operator () (int x) {
		return ((LL) x * a + b) % mod;
	}
} pre[2][MAXN];
int to[256];
func fs[2][4];
int n;
char buf[MAXN];
typedef std::pair<int, int> pi;
std::map<pi, int> S;
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n >> buf + 1;
	to['+'] = 0, to['-'] = 1, to['<'] = 2, to['>'] = 3;
	const int x1 = rd() % (mod - 1) + 1, inv1 = fastpow(x1, mod - 2);
	const int x2 = rd() % (mod - 1) + 1, inv2 = fastpow(x2, mod - 2);
	fs[0][0] = func(1, 1), fs[1][0] = func(1, 1);
	fs[0][1] = func(1, mod - 1), fs[1][1] = func(1, mod - 1);
	fs[0][2] = func(x1, 0), fs[1][2] = func(x2, 0);
	fs[0][3] = func(inv1, 0), fs[1][3] = func(inv2, 0);
	pre[0][0] = pre[1][0] = func(1, 0);
	for (int i = 1; i <= n; ++i) {
		int tar = to[buf[i]];
		pre[0][i] = pre[0][i - 1] + fs[0][tar];
		pre[1][i] = pre[1][i - 1] + fs[1][tar];
	}
	LL ans = 0;
	for (int i = 1; i <= n; ++i) {
		++S[pi((pre[0][i - 1] + pre[0][n])(0), (pre[1][i - 1] + pre[1][n])(0))];
		ans += S[pi(pre[0][i](0), pre[1][i](0))];
	}
	std::cout << ans << std::endl;
	return 0;
}