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;
typedef long long ll;
typedef pair<ll, ll> l_l;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
ll mod[2] = {1000000007, 998244353};
ll base[2] = {532345034, 783920481};
//ll base[2] = {2, 3};
ll N;
string S;
ll pos[260000];
ll rh[260000][2];
map<l_l, ll> mp;

ll beki(ll a, ll b, ll mod) {
    if(b == 0) return 1;
    if(b < 0) {
        ll INV = beki(a, -b, mod);
        return beki(INV, mod - 2, mod);
    }
    ll ret = beki(a, b / 2, mod);
    ret = ret * ret % mod;
    if(b % 2 == 1) {
        ret = ret * a % mod;
    }
    return ret;
}

int main() {
    //cout.precision(10);
    cin >> N;
    cin >> S;
    S = "#" + S;
    for(int index = 0; index <= 1; index++) {
        for(int i = 1; i <= N; i++) {
            pos[i] = pos[i - 1];
            rh[i][index] = rh[i - 1][index];
            if(S[i] == '<') {
                pos[i]--;
            }
            if(S[i] == '>') {
                pos[i]++;
            }
            if(S[i] == '+') {
                rh[i][index] = (rh[i][index] + beki(base[index], pos[i], mod[index])) % mod[index];
            }
            if(S[i] == '-') {
                rh[i][index] = (mod[index] + rh[i][index] - beki(base[index], pos[i], mod[index])) % mod[index];
            }
            //cerr << i << " " << pos[i] << " " << rh[i][index] << endl;
        }
    }
    for(int i = 0; i <= N; i++) {
        //cerr << i << " " << rh[i][0] << " " << rh[i][1] << endl;
    }
    ll ans = 0;
    for(int i = N - 1; i >= 0; i--) {
        ll HASH[2];
        for(int j = 0; j <= 1; j++) {
            //HASH[j] = (rh[N][j] - rh[i + 1][j] + mod[j]) % mod[j];
            HASH[j] = rh[i + 1][j];
        }
        mp[{HASH[0], HASH[1]}]++;
        //cerr << "ADDED " << HASH[0] << " " << HASH[1] << endl;
        for(int j = 0; j <= 1; j++) {
            HASH[j] = rh[i][j] + beki(base[j], pos[i], mod[j]) * rh[N][j];
            HASH[j] %= mod[j];
            //HASH[j] = (mod[j] - HASH[j]) % mod[j];
        }
        //cerr << "SEARCHING " << HASH[0] << " " << HASH[1] << endl;
        ans += mp[{HASH[0], HASH[1]}];
    }
    cout << ans << endl;
    return 0;
}