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 <map>
#include <cstdio>
#include <iostream>

using namespace std ;

typedef long long LL ;


#define mkp make_pair
#define pll pair<LL, LL>

const LL B1 = 237ll ;
const LL B2 = 637ll ;
const int N = 300010 ;
const LL P1 = 998244353 ;
const LL P2 = 1004535809 ;

int n ;
LL ans ;
char s[N] ;
LL I1, I2 ;
LL S[N], T[N] ;
map <pll, LL> buc ;

LL expow(LL a, LL b, LL p){
    LL ret = 1 ;
    while (b){
        if (b & 1)
            (ret *= a) %= p ;
        (a *= a) %= p ; b >>= 1 ;
    }
    return ret ;
}
int main(){
    cin >> n >> (s + 1) ;
    I1 = expow(B1, P1 - 2, P1) ;
    I2 = expow(B2, P2 - 2, P2) ;
    for (int i = n ; i >= 1 ; -- i){
        if (s[i] == '-'){
            S[i] = (S[i + 1] - B1 + P1) % P1 ;
            T[i] = (T[i + 1] - B2 + P2) % P2 ;
        }
        if (s[i] == '+'){
            S[i] = (S[i + 1] + B1) % P1 ;
            T[i] = (T[i + 1] + B2) % P2 ;
        }
        if (s[i] == '<'){
            S[i] = (S[i + 1] * I1) % P1 ;
            T[i] = (T[i + 1] * I2) % P2 ;
        }
        if (s[i] == '>'){
            S[i] = (S[i + 1] * B1) % P1 ;
            T[i] = (T[i + 1] * B2) % P2 ;
        }
        //cout << S[i] << " " << T[i] << endl ;
    }
    LL gs = 1, gt = 1 ;
    for (int i = n ; i >= 1 ; -- i){
        LL x, y ;
        x = expow(gs, P1 - 2, P1) * (-S[i + 1] + P1) % P1 ;
        y = expow(gt, P2 - 2, P2) * (-T[i + 1] + P2) % P2 ;
        if (x < 0) x += P1 ; if (y < 0) y += P2 ; ++ buc[mkp(x, y)] ;
        //cout << x << " " << y << endl ;
        if (s[i] == '<') (gs *= I1) %= P1, (gt *= I2) %= P2 ;
        if (s[i] == '>') (gs *= B1) %= P1, (gt *= B2) %= P2 ;
        x = expow(gs, P1 - 2, P1) * (-S[i] + S[1]) % P1 ;
        y = expow(gt, P2 - 2, P2) * (-T[i] + T[1]) % P2 ;
        if (x < 0) x += P1 ; if (y < 0) y += P2 ; ans += buc[mkp(x, y)] ;
    }
    cout << ans << endl ; return 0 ;
}