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;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=250020;
const ll MOD1=1000000007;
const ll MOD2=1000000009;
const ll p=250007;
ll N,lux1[2*MAX],lux2[2*MAX],ptarr[MAX],ans;
char S[MAX];
map<pll,ll> cum;
ll power(ll x,ll y,ll m){
    if(y==0) return 1;
    ll t=power(x,y/2,m);
    if(y%2) return t*t%m*x%m;
    return t*t%m;
}
void dc(ll idx,ll mul,ll *pt,ll* val1,ll* val2){
    switch(S[idx]){
    case '<':
        *pt-=1; break;
    case '>':
        *pt+=1; break;
    case '+':
        *val1+=mul*lux1[*pt];
        *val2+=mul*lux2[*pt];
        break;
    case '-':
        *val1-=mul*lux1[*pt];
        *val2-=mul*lux2[*pt];
        break;
    }
    *val1+=MOD1,*val1%=MOD1;
    *val2+=MOD2,*val2%=MOD2;
}
int main(){
    scanf(" %lld %s",&N,S);
    lux1[N]=1,lux2[N]=1;
    int inv_p1=power(p,MOD1-2,MOD1),inv_p2=power(p,MOD2-2,MOD2);
    for(ll i=N;i<=2*N-1;i++) {
        lux1[i+1]=lux1[i]*p%MOD1;
        lux2[i+1]=lux2[i]*p%MOD2;
    }
    for(ll i=N;i>=1;i--) {
        lux1[i-1]=lux1[i]*inv_p1%MOD1;
        lux2[i-1]=lux2[i]*inv_p2%MOD2;
    }
    ll pt1=N,pt2=N;
    pll val1(0,0),val2(0,0),val3(0,0);
    for(ll i=0;i<N;i++) dc(i,1,&pt2,&val2.first,&val2.second);
    pt2=N; val3=val2;
    for(ll i=0;i<N;i++){
        ll t1,t2;
        t1=((val3.first-val3.first*lux1[pt1]-val1.first)%MOD1+MOD1)%MOD1;
        t2=((val3.second-val3.second*lux2[pt1]-val1.second)%MOD2+MOD2)%MOD2;
        cum[make_pair(t1,t2)]++;
        dc(i,-1,&pt2,&val2.first,&val2.second);
        //printf("val2: %lld %lld %lld\n",pt2,t1,t2);
        //printf("val1: %lld %lld %lld\n",pt1,val1.first,val1.second);
        ans+=cum[val2];
        dc(i,1,&pt1,&val1.first,&val1.second);
    }
    printf("%lld\n",ans);
}