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 pint = pair<int, int>;
#define x first
#define y second

ostream& operator<<(ostream &st, const pint p) {
    st << "(" << p.x << ", " << p.y << ")";
    return st;
}

const int mod = 1610612741, x1 = 921, x2 = 1209;

string s;
int n, a[250004];
pint p[250004];

int add(int x, int y) { return (x+(long long)y+mod) % mod; }
int mul(int x, int y) { return (x*(long long)y) % mod; }
int power(int x, int k) {
    if (k<0) k += mod-1;
    if (k==0) return 1;
    if (k%2) return mul(x, power(x, k-1));
    int t = power(x, k/2);
    return mul(t, t);
}

int main() {
    cin >> n >> s;

    s = " " + s;

    for (int i=1; i<=n; i++) {
        a[i] = a[i-1];
        if (s[i] == '>') a[i]++;
        if (s[i] == '<') a[i]--;
    }

    int k1 = 0, k2 = 0;
    for (int i=1; i<=n; i++) {
        if (s[i] == '+') k1 = add(k1, power(x1, a[i])), k2 = add(k2, power(x2, a[i]));
        if (s[i] == '-') k1 = add(k1,-power(x1, a[i])), k2 = add(k2,-power(x2, a[i]));
        p[i] = pint(k1, k2);
    }

    map<pint, int> m;
    long long ans = 0;
    for (int i=0; i<=n; i++) {
        if (i) ans += m[p[i]];
        m[pint(add(p[i].x, mul(p[n].x, power(x1, a[i]))), add(p[i].y, mul(p[n].y, power(x2, a[i]))))] += 1;
    }

    cout << ans << '\n';
}