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 <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

const int N=2.5e5+5;

int n;
ll h[3],w[3],ha[3],p[N][3],k[N][3],b[N][3];
ll base[3]={7,29,47},inv[3]={142857144,481911067,13933357},P[3]={1000000007,998244353,19260817};
char st[N];

ll pwr(ll x,ll y,ll P) {
	ll z=1;
	for(;y;y>>=1,x=x*x%P)
		if (y&1) z=z*x%P;
	return z;
}

struct Node{
	ll h[3];
	friend bool operator < (Node a,Node b) {
		fo(i,0,2) {
			if (a.h[i]<b.h[i]) return 1;
			if (a.h[i]>b.h[i]) return 0;
		}
		return 0;
	}
}a;

map<Node,int> mp;

int main() {
	scanf("%d",&n);
	scanf("%s",st+1);
	fd(i,n,1) {
		fo(j,0,2) {
			if (st[i]=='+') h[j]=(h[j]+1)%P[j];
			if (st[i]=='-') h[j]=(h[j]+P[j]-1)%P[j];
			if (st[i]=='>') h[j]=h[j]*base[j]%P[j];
			if (st[i]=='<') h[j]=h[j]*inv[j]%P[j];
		}
	}
	fo(j,0,2) w[j]=1;
	fo(i,1,n) {
		fo(j,0,2) {
			p[i][j]=p[i-1][j];
			if (st[i]=='+') p[i][j]=(p[i][j]+w[j])%P[j];
			if (st[i]=='-') p[i][j]=(p[i][j]+P[j]-w[j])%P[j];
			if (st[i]=='>') w[j]=w[j]*base[j]%P[j];
			if (st[i]=='<') w[j]=w[j]*inv[j]%P[j];
		}
	}
	fo(j,0,2) k[0][j]=1;
	fo(i,1,n) {
		fo(j,0,2) {
			b[i][j]=b[i-1][j];k[i][j]=k[i-1][j];
			if (st[i]=='+') b[i][j]=(b[i][j]+P[j]-1)%P[j];
			if (st[i]=='-') b[i][j]=(b[i][j]+1)%P[j];
			if (st[i]=='>') b[i][j]=b[i][j]*inv[j]%P[j],k[i][j]=k[i][j]*base[j]%P[j];
			if (st[i]=='<') b[i][j]=b[i][j]*base[j]%P[j],k[i][j]=k[i][j]*inv[j]%P[j]; 
		}
	}
	ll ans=0;
	fd(i,n,1) {
		fo(j,0,2) a.h[j]=p[i][j];mp[a]++;
		fo(j,0,2) a.h[j]=(h[j]-b[i-1][j]+P[j])*k[i-1][j]%P[j];
		ans+=mp[a];
	}
	printf("%lld\n",ans);
	return 0;
}