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;

#define int long long

const int   N   = 5e5 + 1;
const int   B   = 1e8 + 1;

typedef pair<int,int>   ii;
typedef pair<ii,ii>     pii;

int qpow(int a,int exp,int mod) {
    if(exp < 0) exp = mod - 1 + exp;
    int ans = 1;
    while (exp) {
        if(exp & 1) ans = ans * a % mod;
        a = a * a % mod;  exp >>= 1;
    }
    return ans;
}

void add(int &a,int b,int mod) {
    a += b;
    if(a >= mod)a -= mod;
    if(a < 0)   a += mod;
}

int mod[4];
int n, f[N];
int H[N][4];
string S;

void process(int t)   {
    for(int i = 1 ; i <= n ; ++i)   {
        H[i][t] = H[i - 1][t];
        if(S[i - 1] == '+') add(H[i][t], qpow(B,f[i],mod[t]),mod[t]);
        if(S[i - 1] == '-') add(H[i][t],-qpow(B,f[i],mod[t]),mod[t]);
    }
}

map<pii,int> mp;

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> S;

    for(int i = 0 ; i < n ; ++i)    {
        f[i + 1] = f[i];
        if(S[i] == '>') f[i + 1]++;
        if(S[i] == '<') f[i + 1]--;
    }

    mod[0] = 1e9 + 7;
    mod[1] = 1e9 + 9;
    mod[2] = 1e9 + 21;
    mod[3] = 1e9 + 33;

    process(0);
    process(1);
    process(2);
    process(3);

    mp[pii({H[n][0],H[n][1]},{H[n][2],H[n][3]})] = 1;

    int ans = 0;

    for(int i = 1 ; i <= n ; ++i)   {
        ans += mp[pii({H[i][0],H[i][1]},{H[i][2],H[i][3]})];
        int res0 = H[n][0] * qpow(B,f[i],mod[0]) + H[i][0];
        int res1 = H[n][1] * qpow(B,f[i],mod[1]) + H[i][1];
        int res2 = H[n][2] * qpow(B,f[i],mod[2]) + H[i][2];
        int res3 = H[n][3] * qpow(B,f[i],mod[3]) + H[i][3];
        res0 %= mod[0]; res1 %= mod[1];
        res2 %= mod[2]; res3 %= mod[3];
        mp[pii({res0,res1},{res2,res3})]++;
    }

    cout << ans << endl;
}