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>
#define pi 3.1415926535897932384626
using namespace std;
      
struct P{
  int x,y;
  bool operator < (const P &a )const{
    //if(y!=a.y)
    return y>a.y;
  };

};

int a,b,c,d,i,n,m,e,dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1};
long long o[251010],o1[251010];
int l[251011];
long long s[251011],re[251010];
long long s1[251011],re1[251010];
long long x,y,z,mod=1000000007,hf=(mod+1)/2;

//string r,r1;
char r[251011];
 vector<int> v[1],v1;
P u[1];
queue<int> q;
//set<int> s[2];
//stack<long long> s;
map<long long,int> p;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//rng()
bool as(P a,P b)
{
  return a.x<b.x;
}

long long po1(long long x,long long y)
{
  long long p=1;
  for(;y;y/=2,x*=x,x%=mod)
  if(y%2)
  {
    p*=x,p%=mod;
  }
  return p;
}

long long po(long long x,long long y)
{
  long long p=1;
  for(;y;y/=2,x*=x,x%=z)
  if(y%2)
  {
    p*=x,p%=z;
  }
  return p;
}

long long f1(int n)
{
  if(n<0) return re1[abs(n)];
  return s1[n];
}

long long f(int n)
{
  if(n<0) return re[abs(n)];
  return s[n];
}

int main()
{
  scanf("%d %s",&a,r+1);
  z=1000000021;
  s[0]=re[0]=s1[0]=re1[0]=1;
  for(int t=1;t<=a;t++)
  {
    s[t]=s[t-1]*3*a%z,re[t]=po(s[t],z-2);
    s1[t]=s1[t-1]*3*a%mod,re1[t]=po1(s1[t],mod-2);
  }
  long long x1=0;
  for(int t=1;t<=a;t++)
  {
    if(r[t]=='+') x+=f(n),x%=z,x1+=f1(n),x1%=mod;
    else if(r[t]=='-') x+=(-f(n)+z),x%=z,x1+=(-f1(n)+mod),x1%=mod;
    else if(r[t]=='>') n++;
    else n--;
    l[t]=n;
    o[t]=x;
    o1[t]=x1;
  }
  long long k=0,y1=x1;
  y=x;
  for(int t=a;t;t--)
  {
    p[o[t]*mod+o1[t]]++;
    k+=p[(o[t-1]+y*f(l[t-1])%z)%z*mod+(o1[t-1]+y1*f1(l[t-1])%mod)%mod];
    //printf("%lld %lld %lld\n",k,o1[t],(o1[t-1]+y1*f1(l[t-1])%mod)%mod);
  }
  printf("%lld",k);
}