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 = 2e5 + 5;
const int mod = 1e9 + 7;
const int modd = 1e9 + 9;
const int X = 1000003;
const int XX = 1000007;
typedef long long ll;
#define mp make_pair


char c;
string s;
ll n,i,t,tt,a,b,aa,bb,x,xx,bol=1,boll=1,ans;
map < pair < int , int > , int > M;

int main(){
    cin >> n >> s;
    for(t=X,i=mod-2; i ; i>>=1){
        if(i & 1) bol = bol*t % mod;
        t = t*t % mod;
    }
    for(t=XX,i=modd-2; i ; i>>=1){
        if(i & 1) boll = boll*t % modd;
        t = t*t % modd;
    }

    for(i=n-1; i>=0 ;i--){
        c = s[i];
        if(c == '+') xx++;
        if(c == '-') xx--;
        if(c == '>') xx *= XX;
        if(c == '<') xx *= boll;
        xx = (xx % modd + modd) % modd;
        if(c == '-') x--;
        if(c == '+') x++;
        if(c == '>') x *= X;
        if(c == '<') x *= bol;
        x = (x % mod + mod) % mod;
    }

    a = 1; b = 0;
    aa = 1;
    M[mp(0,0)] = 1;
    for(i=n-1; i>=0 ;i--){
        c = s[i];
        if(c == '+') b -= a, bb -= aa;
        if(c == '-') b += a, bb += aa;
        if(c == '>') a *= bol, aa *= boll;
        if(c == '<') a *= X, aa *= XX;
        a = (a % mod + mod) % mod;
        b = (b % mod + mod) % mod;
        aa = (aa % modd + modd) % modd;
        bb = (bb % modd + modd) % modd;


        t = (a*x + b) % mod;
        tt = (aa*xx + bb) % modd;

        ans += M[mp(t,tt)];
        M[mp(b,bb)]++;
    }

    cout << ans;
    return 0;
}