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<cstdio>
#define N 250052
#define p 1000000007
#define q 19260817
inline int mod(int x){return x<p?x:x-p;}
char s[N];int A[q],B[N],D[N],T,a[N],b[N],c[N],d[N],i,j,n;long long C[N],z;
inline int Hash(long long x)
{
    int y=x%q;
    for(j=A[y];j;j=B[j])if(C[j]==x)return j;
    return 0;
}
inline void add(long long x)
{
    int y=Hash(x);
    !y?B[++T]=A[y=x%q],C[A[y]=T]=x,D[T]=1:D[y]++;
}
int main()
{
    scanf("%d%s",&n,s+1);
    for(*a=*c=i=1;i<=n;i++)
    if(s[i]=='+')a[i]=a[i-1],b[i]=mod(a[i-1]+b[i-1]),c[i]=c[i-1],d[i]=mod(c[i-1]+d[i-1]);
    else if(s[i]=='-')a[i]=a[i-1],b[i]=mod(p+b[i-1]-a[i-1]),c[i]=c[i-1],d[i]=mod(p+d[i-1]-c[i-1]);
    else if(s[i]=='>')a[i]=998244353ll*a[i-1]%p,b[i]=b[i-1],c[i]=499122177ll*c[i-1]%p,d[i]=d[i-1];
    else a[i]=4924091ll*a[i-1]%p,b[i]=b[i-1],c[i]=229537957ll*c[i-1]%p,d[i]=d[i-1];
    for(i=1;i<=n;i++)add(((long long)b[n]*a[i-1]+b[i-1])%p*p+((long long)d[n]*c[i-1]+d[i-1])%p),z+=D[Hash((long long)b[i]*p+d[i])];
    return 0*printf("%lld\n",z);
}