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;

typedef long long ll;

const ll MOD1 = 998244353;
const ll MOD2 = 1000000009;
const int MX = 250005;
const ll R1 = 123123;
const ll IR1 = 981323583;
const ll R2 = 321321;
const ll IR2 = 234033881;

ll qpow(ll x, ll t, ll p)
{
	ll ans = 1;
	while(t)
	{
		if(t & 1) ans = ans*x % p;
		x = x*x % p;
		t >>= 1;
	}
	return ans;
}

ll inv(ll x, ll p)
{
	return qpow(x, p-2, p);
}

struct NUM
{
	ll x, y;

	NUM (const ll &x0 = 0, const ll &y0 = 0) : x(x0), y(y0) {}
	NUM operator + (const NUM &t) const {return NUM((x+t.x)%MOD1, (y+t.y)%MOD2);}
	NUM operator - (const NUM &t) const {return NUM((x-t.x+MOD1)%MOD1, (y-t.y+MOD2)%MOD2);}
	NUM operator * (const NUM &t) const {return NUM((x*t.x)%MOD1, (y*t.y)%MOD2);}
	bool operator == (const NUM &t) const {return x==t.x && y==t.y;}
	bool operator < (const NUM &t) const {return (x!=t.x) ? (x<t.x) : (y<t.y);}
};

int n;
char str[MX];

void input()
{
	scanf("%d", &n);
	scanf("%s", str+1);
}

NUM con[MX], sum[MX];
map<NUM, int> hav;

void work()
{
	NUM p(1, 1), t(1, 1), r(R1, R2), ir(IR1, IR2);
	for(int i=1; i<=n; i++)
	{
		if(str[i] == '+') con[i] = p;
		else if(str[i] == '-') con[i] = NUM(0, 0) - p;
		else if(str[i] == '>') p = p * r;
		else p = p * ir;
		sum[i] = sum[i-1] + con[i];
		hav[sum[i]]++;
	}
	ll ans = 0;
	for(int i=1; i<=n; i++)
	{
		ans += hav[sum[n]*t+sum[i-1]];
		if(str[i] == '>') t = t * r;
		else if(str[i] == '<') t = t * ir;
		hav[sum[i]]--;
	}
	printf("%lld\n", ans);
}

int main()
{
	input();
	work();
	return 0;
}