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<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
typedef unsigned long long ll;
typedef double dd;
typedef __int128 I;
#define For(i,j,k) for (int i=(int)j;i<=(int)k;++i)
#define Forr(i,j,k) for (int i=(int)j;i>=(int)k;--i)
#define Set(a,p) memset(a,p,sizeof(a))
using namespace std;

template<typename T>bool chkmax(T &a,T b) { return a<b?a=b,1:0; }
template<typename T>bool chkmin(T &a,T b) { return a>b?a=b,1:0; }

const int maxn=250000+100;
const ll modd=1000000000000000031ll;
const ll p1=1000000000000000003ll;
const ll p2=821428571428571454ll;
int n;
ll Ans;
ll p[maxn],a[maxn];
char s[maxn];
map<ll,int>ma;

inline void file() {
	freopen("ARC099F.in","r",stdin);
	freopen("ARC099F.out","w",stdout);
}

inline ll quick(ll a,ll b) {
	ll s=1;
	while (b) {
		if (b%2==1) s=(I)s*a%modd;
		a=(I)a*a%modd; b/=2;
	}
	return s;
}

int main() {
//	file();
	scanf("%d",&n);
	scanf("%s",s+1);
	p[0]=1;
	For (i,1,n) {
		p[i]=p[i-1]; a[i]=a[i-1];
		if (s[i]=='+') a[i]=((I)a[i]+p[i])%modd;
		if (s[i]=='-') a[i]=((I)a[i]+modd-p[i])%modd;
		if (s[i]=='>') p[i]=(I)p[i]*p1%modd;
		if (s[i]=='<') p[i]=(I)p[i]*p2%modd;
	}
	Forr (i,n,1) {
		++ma[a[i]];
		Ans+=ma[((I)a[n]*p[i-1]%modd+a[i-1])%modd];
	}
	printf("%lld",Ans);
	return 0;
}