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;

using lint = long long int;
using P = pair<lint, lint>;

constexpr lint MOD = 1000000007;

vector<lint> X{250007, 861743};
vector<lint> Xinv(2);

int N;
string S;

// ax+by=gcd(a, b)
template <typename T>
T extgcd(T a, T b, T &x, T &y)
{
    T d = a;
    if (b != 0)
    {
        d = extgcd(b, a % b, y, x);
        y -= a / b * x;
    }
    else
    {
        x = 1;
        y = 0;
    }
    return d;
}

P nxt_hash(P prev_hash, lint x, lint xinv, char c)
{
    P res = prev_hash;
    if (c == '+')
    {
        res.first++;
    }
    if (c == '-')
    {
        res.first += MOD - 1;
    }
    if (c == '>')
    {
        res.first *= x;
        res.second *= x;
    }
    if (c == '<')
    {
        res.first *= xinv;
        res.second *= xinv;
    }
    res.first %= MOD;
    res.second %= MOD;
    return res;
}

int main()
{
    for (int i = 0; i < 2; i++)
    {
        lint xinv, tmp;
        extgcd(X[i], MOD, xinv, tmp);
        Xinv[i] = (xinv + MOD) % MOD;
    }

    cin >> N >> S;

    vector<vector<P> > hash(2, vector<P>(N+1, make_pair(0LL, 1LL)));

    for (unsigned ix = 0; ix < 2; ix++)
    {
        lint x = X[ix];
        lint xinv = Xinv[ix];
        for (int i = N - 1; i>=0; i--) hash[ix][i] = nxt_hash(hash[ix][i + 1], x, xinv, S[i]);
    }

    for (int ix = 0; ix < 2; ix++)
    {
        for (int i = 0; i <= N; i++)
        {
            lint invh, tmp;
            extgcd(hash[ix][i].second, MOD, invh, tmp);
            hash[ix][i].second = (invh + MOD) % MOD;
        }
    }

    lint ans = 0;
    map<P, int> hash_lst;
    for (int m = N; m >= 0; m--)
    {
        P h_query;
        h_query.first = (hash[0][m].first - hash[0][0].first + MOD) * hash[0][m].second % MOD;
        h_query.second = (hash[1][m].first - hash[1][0].first + MOD) * hash[1][m].second % MOD;

        ans += hash_lst[h_query];

        P h_append;
        h_append.first = hash[0][m].first * hash[0][m].second % MOD;
        h_append.second = hash[1][m].first * hash[1][m].second % MOD;
        hash_lst[h_append]++;
    }

    cout << ans << endl;

    return 0;
}