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:
// No.190049041520
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mk make_pair
#define fi first
#define se second
#define N 500500
const int b1 = 7546823, m1 = 277425539;
const int b2 = 1000033, m2 = 277444379;

inline void inc(int &x, const int &y, const int &Mod) {
    x = (x + y) % Mod;
}

inline int fsp(int x, int k, int p) {
    if (k < 0) k += p - 1;
    int res = 1;
    while (k) {
        if (k & 1) res = 1ll * res * x % p;
        x = 1ll * x * x % p, k >>= 1;
    }
    return res;
}

int n, po1[N], po2[N];
char s[N];
pii h[N];
map<pii, int> num;

int main() {
#ifdef isLOCAL
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif

    cin >> n;
    scanf("%s", s + 1);

    int p1 = po1[0] = 1, p2 = po2[0] = 1, c1 = 0, c2 = 0, i1, i2;
    i1 = fsp(b1, -1, m1), i2 = fsp(b2, -1, m2);
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '+') inc(c1, p1, m1), inc(c2, p2, m2);
        if (s[i] == '-') inc(c1, m1 - p1, m1), inc(c2, m2 - p2, m2);
        if (s[i] == '<') p1 = 1ll * p1 * i1 % m1, p2 = 1ll * p2 * i2 % m2;
        if (s[i] == '>') p1 = 1ll * p1 * b1 % m1, p2 = 1ll * p2 * b2 % m2;
        if (c1 < 0) c1 += m1;
        if (c2 < 0) c2 += m2;
        po1[i] = p1, po2[i] = p2;
        h[i] = mk(c1, c2);
    }

    long long ans = 0; ++num[h[n]];
    for (int i = n - 1, tc1, tc2; i >= 0; --i) {
        tc1 = (h[i].fi + 1ll * po1[i] * h[n].fi) % m1;
        tc2 = (h[i].se + 1ll * po2[i] * h[n].se) % m2;
        ans += num[mk(tc1, tc2)], ++num[h[i]];
    }

    cout << ans << endl;

    return 0;
}