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;
const int N=1e6+5;
const int mod1=1e9+7;
const int P1=19260817;
const int P2=998244353;
const int mod2=1004535809;
#define ll long long
typedef pair<ll,ll>Pi;
ll fsp(ll x,int y){
    ll ans=1;
    while(y){
        if(y&1) ans=ans*x%mod1;
        x=x*x%mod1,y>>=1;
    }
    return ans;
}
ll ksm(ll x,int y){
    ll ans=1;
    while(y){
        if(y&1) ans=ans*x%mod2;
        x=x*x%mod2,y>>=1;
    }
    return ans;
}
char s[N];
map<Pi,int>ma;
ll n,l1,l2=1,r1,r2=1,ans,res1,res2,add1,add2,inv1,inv2;
int main(){
    scanf("%lld%s",&n,s+1);
    add1=fsp(P1,n);add2=ksm(P2,n);
    inv1=fsp(P1,mod1-2),inv2=ksm(P2,mod2-2);
    for(int i=n;i;i--){
        if(s[i]=='-'){
            res1=(res1-add1+mod1)%mod1;
            res2=(res2-add2+mod2)%mod2;
        }
        if(s[i]=='+'){
            res1=(res1+add1)%mod1;
            res2=(res2+add2)%mod2;
        }
        if(s[i]=='<'){
            res1=res1*inv1%mod1;
            res2=res2*inv2%mod2;
        }
        if(s[i]=='>'){
            res1=res1*P1%mod1;
            res2=res2*P2%mod2;
        }
    }
    for(int i=n;i;i--){
        ll k1=0,k2=0;
        if(s[i]=='-'){
            l1=(l1-add1+mod1)%mod1,k1=mod1-add1;
            r1=(r1-add2+mod2)%mod2,k2=mod2-add2;
        }
        if(s[i]=='<'){
            l1=l1*inv1%mod1,l2=l2*inv1%mod1;
            r1=r1*inv2%mod2,r2=r2*inv2%mod2;
        }
        if(s[i]=='>'){
            l1=l1*P1%mod1,l2=l2*P1%mod1;
            r1=r1*P2%mod2,r2=r2*P2%mod2;
        }
        if(s[i]=='+'){
            l1=(l1+add1)%mod1,k1=add1;
            r1=(r1+add2)%mod2,k2=add2;
        }
        ++ma[Pi((k1-l1+mod1)*fsp(l2,mod1-2)%mod1,(k2-r1+mod2)*ksm(r2,mod2-2)%mod2)];
        ans+=ma[Pi((res1-l1+mod1)*fsp(l2,mod1-2)%mod1,(res2-r1+mod2)*ksm(r2,mod2-2)%mod2)];
    }
    printf("%lld\n",ans);
    return 0;
}