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
#define fi first
#define se second

const int mod0 = 1e9 + 9, mod1 = 1e9 + 7, base = 500005;
int n, pwbase[2][base], hashs[2][base], cur = 250000, ans, start[base];
string s;
map< pair<int, int>, int> cnt;

int binpw (int aa, int mm, int mod) {
    int ret = 1;
    for (; mm; mm >>= 1, aa = (aa * aa) % mod) if (mm & 1) ret = (ret * aa) % mod;
    return ret;
}

signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s; s = '*' + s;
    pwbase[0][0] = pwbase[1][0] = 1;
    for (int i = 1; i < base; ++i) {
        pwbase[0][i] = (pwbase[0][i - 1] * base) % mod0;
        pwbase[1][i] = (pwbase[1][i - 1] * base) % mod1;
    }
    for (int i = 1; i <= n; ++i) {
        start[i] = cur;
        if(s[i] == '<') cur --;
        else if(s[i] == '>') cur ++;
        hashs[0][i] = hashs[0][i - 1];
        hashs[1][i] = hashs[1][i - 1];
        if (s[i] == '+') {
            hashs[0][i] = (hashs[0][i] + pwbase[0][cur]) % mod0;
            hashs[1][i] = (hashs[1][i] + pwbase[1][cur]) % mod1;
        }
        else if (s[i] == '-') {
            hashs[0][i] = ( (hashs[0][i] - pwbase[0][cur]) % mod0 + mod0) % mod0;
            hashs[1][i] = ( (hashs[1][i] - pwbase[1][cur]) % mod1 + mod1) % mod1;
        }
    }

    pair<int, int> X = { (hashs[0][n] * binpw(pwbase[0][ start[1] ], mod0 - 2, mod0) ) % mod0,
                        (hashs[1][n] * binpw(pwbase[1][ start[1] ], mod1 - 2, mod1)) % mod1 };

    for (int i = n; i > 0; --i) {
        cnt[ { hashs[0][i], hashs[1][i] } ] ++;
        ans += cnt[ { (X.fi * pwbase[0][ start[i] ] + hashs[0][i - 1]) % mod0, (X.se * pwbase[1][ start[i] ] + hashs[1][i - 1]) % mod1 } ];
    }

    cout << ans;

    return 0;
}