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 <iostream>
#include <cstdio>
#include <map>
#define int long long
using namespace std;
const int N = 3e5 + 5;
const int B1 = 23711, B2 = 63711, P1 = 998244353, P2 = 1004535809;
int n, S[N], T[N], f[N][2], inv1, inv2, ans;
map<pair<int, int>, int> t;
char s[N];
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int ksm(int x, int y, int mod)
{
	int res = 1;
	for(; y; y >>= 1, x = x * x % mod)
		if(y & 1) res = res * x % mod;
	return res;
}
signed main()
{
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	n = read(); scanf("%s", s + 1); f[0][0] = f[0][1] = 1;
	inv1 = ksm(B1, P1 - 2, P1); inv2 = ksm(B2, P2 - 2, P2);
	for(int i = 1; i <= n; i ++)
	{
		if(s[i] == '-')
		{
			f[i][0] = f[i - 1][0]; f[i][1] = f[i - 1][1];
			S[i] = (S[i - 1] - f[i][0] + P1) % P1;
			T[i] = (T[i - 1] - f[i][1] + P2) % P2;
		}
		else if(s[i] == '+')
		{
			f[i][0] = f[i - 1][0]; f[i][1] = f[i - 1][1];
			S[i] = (S[i - 1] + f[i][0]) % P1;
			T[i] = (T[i - 1] + f[i][1]) % P2;
		}
		else if(s[i] == '<')
		{
			f[i][0] = f[i - 1][0] * inv1 % P1;
			f[i][1] = f[i - 1][1] * inv2 % P2;
			S[i] = S[i - 1]; T[i] = T[i - 1];
			
		}
		else if(s[i] == '>')
		{
			f[i][0] = f[i - 1][0] * B1 % P1;
			f[i][1] = f[i - 1][1] * B2 % P2;
			S[i] = S[i - 1]; T[i] = T[i - 1];
		}
		t[make_pair(S[i], T[i])] ++;
	}
	t[make_pair(0, 0)] ++; int x, y;
	for(int i = 0; i < n; i ++)
	{
		t[make_pair(S[i], T[i])] --;
		x = (S[i] + S[n] * f[i][0] % P1) % P1;
		y = (T[i] + T[n] * f[i][1] % P2) % P2;
		ans += t[make_pair(x, y)];
	}
	printf("%lld\n", ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}