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 <cstdio>
#include <map>
typedef long long ll; 
inline ll quick_pow(ll a, ll n, ll mod)
{
	ll res = 1; 
	while (n)
	{
		if (n & 1)
			res = res * a % mod; 
		a = a * a % mod;
		n >>= 1; 
	}
	return res; 
}
struct data
{
	ll arr[5]; 
	inline ll &operator [](const int &x)
	{
		return arr[x]; 
	}
	inline const ll &operator [](const int &x) const
	{
		return arr[x]; 
	}
	inline bool operator <(const data &x) const
	{
		for (int i = 0; i < 5; i++)
		{
			if (arr[i] != x[i])
				return arr[i] < x[i]; 
		}
		return false; 
	}
} hsh[300005], cur; 
std::map<data, int> app; 
const ll bs[] = {1234567, 500003, 500007, 800001, 19260817};
const ll md[] = {998244353, 1000000007, 1000000009, 998244353, 1234567891}; 
int idx[300005]; 
char str[300005]; 
ll pw[5][600005], inv[5][600005]; 
int main()
{
	// freopen("ARC099-F.in", "r", stdin); 
	int n; 
	scanf("%d%s", &n, str);
	for (int i = 0; i < 5; i++)
	{
		pw[i][0] = 1; 
		for (int j = 1; j <= 6e5; j++)
			pw[i][j] = pw[i][j - 1] * bs[i] % md[i];
		inv[i][0] = 1; 
		int x = quick_pow(bs[i], md[i] - 2, md[i]); 
		for (int j = 1; j <= 6e5; j++)
			inv[i][j] = inv[i][j - 1] * x % md[i]; 
	}
	int pos = n + 5; 
	for (int i = 0; i <= n; i++)
	{
		idx[i] = pos; 
		hsh[i] = cur; 
		if (str[i] == '+')
		{
			for (int j = 0; j < 5; j++)
				(cur[j] += pw[j][pos]) %= md[j];
		}
		else if (str[i] == '-')
		{
			for (int j = 0; j < 5; j++)
				(cur[j] += md[j] - pw[j][pos]) %= md[j];
		}
		else if (str[i] == '<')
			pos--;
		else
			pos++; 
	}
	ll ans = 0; 
	for (int i = n; i >= 0; i--)
	{
		data x; 
		int d = idx[i] - (n + 5); 
		if (d >= 0)
		{
			for (int j = 0; j < 5; j++)
				x[j] = (hsh[i][j] + cur[j] * pw[j][d]) % md[j]; 
		}
		else
		{
			for (int j = 0; j < 5; j++)
				x[j] = (hsh[i][j] + cur[j] * inv[j][-d]) % md[j];
		}
		ans += app[x]; 
		app[hsh[i]]++; 
	}
	printf("%lld\n", ans);
	return 0; 
}