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 <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
#define fs first
#define se second

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
typedef pair<ld, ld> pdd;

const int mod = 1e9 + 7, p1 = 17, p2 = 998244353;

int pw(int x, int p) {
    int r = 1;
    while (p) {
        if (p & 1) r = (llong)r * x % mod;
        x = (llong)x * x % mod;
        p >>= 1;
    }
    return r;
}

int n;
char in[250002];
pii S[250001];
int P[250001];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> in + 1;
    for (int i = 1; i <= n; ++i) {
        if (in[i] == '+') {
            P[i] = P[i - 1];
            S[i].fs = (S[i - 1].fs + pw(p1, P[i])) % mod;
            S[i].se = (S[i - 1].se + pw(p2, P[i])) % mod;
        }
        else if (in[i] == '-') {
            P[i] = P[i - 1];
            S[i].fs = (S[i - 1].fs + mod - pw(p1, P[i])) % mod;
            S[i].se = (S[i - 1].se + mod - pw(p2, P[i])) % mod;
        }
        else if (in[i] == '>') {
            P[i] = (P[i - 1] + 1) % (mod - 1);
            S[i] = S[i - 1];
        }
        else {
            P[i] = (P[i - 1] + mod - 2) % (mod - 1);
            S[i] = S[i - 1];
        }
    }
    llong ans = 0;
    map<pii, int> mp;
    for (int i = 0; i <= n; ++i) {
        ans += mp[S[i]];
        pii v(((llong)pw(p1, P[i]) * S[n].fs + S[i].fs) % mod
            , ((llong)pw(p2, P[i]) * S[n].se + S[i].se) % mod);
        ++mp[v];
    }
    printf("%lld\n", ans);
}