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;

ll pow_mod(ll x,int k,ll MOD) {
  ll ans=1;
  while (k) {
  	if (k&1) ans=ans*x%MOD;
  	x=x*x%MOD;
  	k>>=1;
  }
  return ans;
}

const int prime[10]={998244353,989390509,807943519,934784771,814294163,847763881,988501229,831312439,887199301,993514421};
const ll H[10]={19260817,760277961,602494845,909561729,536778743,682353612,738823132,631427472,848965391,984035289};

int powd[10][1000005],invd[10][1000005];

void pre(int n) {
  for(int i=0;i<10;i++) {
    ll inv=pow_mod(H[i],prime[i]-2,prime[i]);
    assert(inv*H[i]%prime[i]==1);
    powd[i][0]=1;
    for(int j=1;j<=n;j++) powd[i][j]=(ll)powd[i][j-1]*H[i]%prime[i];
    invd[i][0]=1;
    for(int j=1;j<=n;j++) invd[i][j]=(ll)invd[i][j-1]*inv%prime[i];
  }
}

struct Data {
  int num[10];
  Data() {memset(num,0,sizeof(num));}
  Data operator + (Data b) {
  	Data c;
  	for(int i=0;i<10;i++) c.num[i]=(num[i]+b.num[i])%prime[i];
  	return c;
  }
  void add(int x) {
  	for(int i=0;i<10;i++) num[i]=(num[i]+powd[i][x])%prime[i];
  }
  void dec(int x) {
  	for(int i=0;i<10;i++) num[i]=(num[i]-powd[i][x]+prime[i])%prime[i];
  }
  void rshift(int x) {
  	for(int i=0;i<10;i++) num[i]=(ll)num[i]*powd[i][x]%prime[i];
  }
  void lshift(int x) {
  	for(int i=0;i<10;i++) num[i]=(ll)num[i]*invd[i][x]%prime[i];
  }
  bool operator < (const Data & b) const {
  	for(int i=0;i<10;i++)
  	  if (num[i]!=b.num[i]) return num[i]<b.num[i];
  	return 0;
  }
};

map <Data,int> mp;
Data p[250005];

char str[250005];

int main() {
  int n;
  scanf("%d%s",&n,str+1);
  pre(4*n);
  int d=0;
  for(int i=1;i<=n;i++) {
  	p[i]=p[i-1];
    if (str[i]=='+') p[i].add(2*n+d);
    else if (str[i]=='-') p[i].dec(2*n+d);
    else if (str[i]=='>') d++;
    else d--;
    mp[p[i]]++;
  }
  ll ans=0;
  d=0;
  for(int i=1;i<=n;i++) {
  	Data t=p[n];
  	if (d>=0) t.rshift(d); else t.lshift(-d);
	t=t+p[i-1];
	if (mp.count(t)) ans+=mp[t];
	if (str[i]=='>') d++;
	else if (str[i]=='<') d--;
	mp[p[i]]--;
  }
  printf("%lld\n",ans);
  return 0;
}