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 ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int MOD = 1000000033, N = 6e5 + 5;

ll bp(ll a, ll p) {
    ll r = 1;
    while (p > 0) {
        if (p & 1)
            r = r * a % MOD;
        a = a * a % MOD;
        p >>= 1;
    }
    return r;
}

ll inv_X[6], X[6];

vector<ll> a[N], b[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    mt19937 rnd(time(0));

    for (int i = 0; i < 6; i++) {
        X[i] = rnd() % 1000000 + 1000000;
        inv_X[i] = bp(X[i], MOD - 2);
    }

    int n;
    string s;
    cin >> n >> s;

    vector<ll> h(6, 0);

    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '>') {
            for (int j = 0; j < 6; j++) {
                h[j] = h[j] * X[j] % MOD;
            }
        }
        else if (s[i] == '<') {
            for (int j = 0; j < 6; j++) {
                h[j] = h[j] * inv_X[j] % MOD;
            }
        }
        else if (s[i] == '+') {
            for (ll &x : h)
                x = (x + 1) % MOD;
        }
        else {
            for (ll &x : h)
                x = (x - 1 + MOD) % MOD;
        }
    }

    map<vector<ll>, int> mp;

    ll ans = 0;

    a[n] = vector<ll>(6, 1);
    b[n] = vector<ll>(6, 0);

    for (int i = n - 1; i >= 0; i--) {
        mp[b[i + 1]]++;

        a[i] = a[i + 1];
        b[i] = b[i + 1];

        if (s[i] == '>') {
            for (int j = 0; j < 6; j++) {
                a[i][j] = a[i][j] * inv_X[j] % MOD;
            }
        }
        else if (s[i] == '<') {
            for (int j = 0; j < 6; j++) {
                a[i][j] = a[i][j] * X[j] % MOD;
            }
        }
        else if (s[i] == '+') {
            for (int j = 0; j < 6; j++) {
                b[i][j] = (b[i][j] - a[i][j] + MOD) % MOD;
            }
        }
        else {
            for (int j = 0; j < 6; j++) {
                b[i][j] = (b[i][j] + a[i][j]) % MOD;
            }
        }

        vector<ll> qr;
        for (int j = 0; j < 6; j++) {
            qr.push_back((a[i][j] * h[j] + b[i][j]) % MOD);
        }

        ans += mp[qr];
    }
    
    cout << ans << "\n";

    return 0;   
}