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 ll=long long;

#define K 6 
#define rep(i) for(int i=0;i<K;i++)
using Token=array<int,K>;

//const ll R = 843823891, iR = 1040004855;
const ll R[K] = {3213,24289,34299,929923,438,42};
const ll iR[K] = {727200786, 1395409909, 1110851529, 35704193, 1005586100, 1598363886};

const ll M = 1637348371;
ll mpow(ll x, int64_t e) {
    ll res = 1;
    for (; e; e >>= 1) {
        if (e & 1) res *= x, res %= M;
        x *= x, x %= M;
    }
    return res;
}
ll minv(ll x) {
    return mpow(x, M-2);
}

struct Lm {
    ll k,b;
    Lm() {}
    Lm(ll _k,ll _b): k(_k),b(_b){}
    Lm(char x, int i) {
        if (x == '+') k = 1, b = 1;
        if (x == '-') k = 1, b = M-1;
        if (x == '>') k = R[i], b = 0;
        if (x == '<') k = iR[i],b = 0;
    }
    Lm(const Lm& _lm): k(_lm.k), b(_lm.b){}
    Lm& operator*=(const Lm& _lm){
        b += k*_lm.b%M; b %= M;
        k *= _lm.k; k %= M;
        return *this;
    }
    Lm inv(){
        ll ik = minv(k);
        ll ib = -ik*b; ib %= M; (ib+=M)%=M;
        return {ik,ib};
    }
    ll eval(ll x) {
        return (k*x%M+b)%M;
    }
};
Lm operator*(const Lm& _a, const Lm& _b) {
    return Lm(_a) *= _b;
}
void solve() {
    int n; cin >> n;
    string s; cin >> s;
    vector<Lm> a[6], ia[6];
    vector<Token> z(n+1), g(n);
    rep(k) {
    for (int i = 0; i < n; i++) {
        a[k].emplace_back(s[i], k);
        ia[k].emplace_back(a[k][i].inv());
    }
    auto isuf = ia;
    for (int i = n-2; i >= 0; i--) {
        isuf[k][i] = isuf[k][i+1] * isuf[k][i];
    }
    ll c = isuf[k][0].inv().eval(0);
    z[n][k] = 0;
    for (int i = 0; i < n; i++) {
        z[i][k] = isuf[k][i].eval(0);
        g[i][k] = isuf[k][i].eval(c);
    }
    }
    map<Token, int> cnt;
    ll res = 0;
    for (int i = 0; i < n; i++) {
        cnt[g[i]]++;
        res += cnt[z[i+1]];
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}