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 g[N][2] ;
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) ;
    g[0][0] = g[0][1] = 1ll ; 
    I1 = expow(B1, P1 - 2, P1) ;
    I2 = expow(B2, P2 - 2, P2) ;
    for (int i = 1 ; i <= n ; ++ i){
        if (s[i] == '-'){
            g[i][0] = g[i - 1][0] ;
            g[i][1] = g[i - 1][1] ;
            S[i] = (S[i - 1] - g[i][0] + P1) % P1 ;
            T[i] = (T[i - 1] - g[i][1] + P2) % P2 ;
        }
        if (s[i] == '+'){
            g[i][0] = g[i - 1][0] ;
            g[i][1] = g[i - 1][1] ;
            S[i] = (S[i - 1] + g[i][0]) % P1 ;
            T[i] = (T[i - 1] + g[i][1]) % P2 ;
        }
        if (s[i] == '<'){
            g[i][0] = g[i - 1][0] * I1 % P1 ;
            g[i][1] = g[i - 1][1] * I2 % P2 ;
            S[i] = S[i - 1] ; T[i] = T[i - 1] ;
        }
        if (s[i] == '>'){
            g[i][0] = g[i - 1][0] * B1 % P1 ;
            g[i][1] = g[i - 1][1] * B2 % P2 ;
            S[i] = S[i - 1] ; T[i] = T[i - 1] ;
        }
		++ buc[mkp(S[i], T[i])] ;
    }
    ++ buc[mkp(0, 0)] ; LL x, y ;
    for (int i = 0 ; i < n ; ++ i){
		buc[mkp(S[i] , T[i])] -- ; 
        x = (S[i] + S[n] * g[i][0] % P1) % P1 ; 
		y = (T[i] + T[n] * g[i][1] % P2) % P2 ;
        ans += buc[mkp(x, y)] ; 
    }
    cout << ans << endl ; return 0 ;
}