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;
#define N 251000
#define ll long long
#define mp make_pair
const ll mod1=1e9+7,mod2=998244353,mod3=19260817;
const ll bas1=2333,bas2=4399,bas3=377,ibas1=461637380,ibas2=924039783,ibas3=18749920;

int n;
ll ans;
char s[N];
ll h1[N],p1[N],h2[N],p2[N],p3[N],h3[N];
map<pair<pair<ll,ll>,ll>,int> m;

ll add1(ll x,ll y) {return (x+y)%mod1;}
ll mul1(ll x,ll y) {return x*y%mod1;}
ll add2(ll x,ll y) {return (x+y)%mod2;}
ll mul2(ll x,ll y) {return x*y%mod2;}
ll add3(ll x,ll y) {return (x+y)%mod3;}
ll mul3(ll x,ll y) {return x*y%mod3;}

int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	p1[0]=1;
	for (int i=1;i<=n;i++) {
		p1[i]=p1[i-1]; h1[i]=h1[i-1];
		if (s[i]=='+') h1[i]=add1(h1[i],p1[i]);
		if (s[i]=='-') h1[i]=add1(h1[i],mod1-p1[i]);
		if (s[i]=='<') p1[i]=mul1(p1[i],ibas1);
		if (s[i]=='>') p1[i]=mul1(p1[i],bas1);
	}
	
	p2[0]=1;
	for (int i=1;i<=n;i++) {
		p2[i]=p2[i-1]; h2[i]=h2[i-1];
		if (s[i]=='+') h2[i]=add2(h2[i],p2[i]);
		if (s[i]=='-') h2[i]=add2(h2[i],mod2-p2[i]);
		if (s[i]=='<') p2[i]=mul2(p2[i],ibas2);
		if (s[i]=='>') p2[i]=mul2(p2[i],bas2);
	}

	p3[0]=1;
	for (int i=1;i<=n;i++) {
		p3[i]=p3[i-1]; h3[i]=h3[i-1];
		if (s[i]=='+') h3[i]=add3(h3[i],p3[i]);
		if (s[i]=='-') h3[i]=add3(h3[i],mod3-p3[i]);
		if (s[i]=='<') p3[i]=mul3(p3[i],ibas3);
		if (s[i]=='>') p3[i]=mul3(p3[i],bas3);
	}
	
	for (int i=n;i;i--) {
		m[mp(mp(h1[i],h2[i]),h3[i])]++;
		ll t1=add1(mul1(h1[n],p1[i-1]),h1[i-1]),t2=add2(mul2(h2[n],p2[i-1]),h2[i-1]),t3=add3(mul3(h3[n],p3[i-1]),h3[i-1]);
		ans+=m[mp(mp(t1,t2),t3)];
	}
	printf("%lld\n",ans);
	return 0;
}