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>

using namespace std;

const int mod1 = 998244353,mod2 = 1000000007;

struct Hsh
{
	long long m1,m2;
	Hsh operator + (const Hsh &a) const
	{
		return (Hsh){(m1 + a.m1) % mod1,(m2 + a.m2) % mod2};
	}
	Hsh operator - (const Hsh &a) const
	{
		return (Hsh){(m1 - a.m1 + mod1) % mod1,(m2 - a.m2 + mod2) % mod2};
	}
	Hsh operator * (const Hsh &a) const
	{
		return (Hsh){m1 * a.m1 % mod1,m2 * a.m2 % mod2};
	}
	bool operator < (const Hsh &a) const
	{
		return m1 == a.m1 ? m2 < a.m2 : m1 < a.m1;
	}
}ha[250050],pos[500050];

map<Hsh,int> mp;
int N;
const int bas1 = 131,bas2 = 1331;
char s[250005];

long long qpow(long long base,int tms,int mod)
{
	long long tmp = 1;
	while(tms)
	{
		if(tms & 1) tmp = tmp * base % mod;
		base = base * base % mod;
		tms >>= 1;
	}
	return tmp;
}

int main()
{
	Hsh x,inv;
	int n;
	x.m1 = bas1,x.m2 = bas2;
	inv.m1 = qpow(bas1,mod1 - 2,mod1),inv.m2 = qpow(bas2,mod2 - 2,mod2);
	pos[0].m1 = pos[0].m2 = 1; scanf("%d",&n); scanf("%s",s + 1);
	for(int i = 1;i <= n; ++ i)
	{
		pos[i] = pos[i - 1];
		if(s[i] == '<') pos[i] = pos[i - 1] * inv;
		else if(s[i] == '>') pos[i] = pos[i - 1] * x;
	}
	for(int i = n;i >= 1; -- i)
	{
		ha[i] = ha[i + 1];
		if(s[i] == '+') ha[i] = ha[i] + pos[i];
		else if(s[i] == '-') ha[i] = ha[i] - pos[i];
	}
	mp[ha[n + 1]] = 1;
	long long ans = 0;
	for(int i = n;i >= 1; -- i)
	{
		Hsh cur = ha[i] - ha[1] * pos[i - 1];
		ans += mp[cur];
		mp[ha[i]] ++;
	}
	printf("%lld\n",ans);
}