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 <cstdio>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L
#define PI 3.141592653589793238462643383279502884L

#define long long long int

using std::vector;
using std::map;
using std::set;
using std::string;
using std::pair;
using std::cin;
using std::cout;
using std::cerr;

// @author: pashka

#define MAX 250000

int main() {
    std::ios::sync_with_stdio(false);

    int n;
    cin >> n;
    string s;
    cin >> s;

    long MOD[2] = {1758706867, 1299697759};
    long X[2] = {716447, 656323};

    vector<vector<long>> pow(2, vector<long>(2 * MAX + 2));
    pow[0][0] = pow[1][0] = 1;
    for (int k = 0; k < 2; k++) {
        for (int i = 1; i < pow[k].size(); i++) {
            pow[k][i] = (pow[k][i - 1] * X[k]) % MOD[k];
        }
    }

    vector<vector<long>> h(2, vector<long>(n + 1));
    vector<int> p(n + 1);
    for (int k = 0; k < 2; k++) {
        p[0] = MAX + 1;
        for (int i = 0; i < n; i++) {
            h[k][i + 1] = h[k][i];
            p[i + 1] = p[i];
            if (s[i] == '+') {
                h[k][i + 1] += pow[k][p[i]];
            } else if (s[i] == '-') {
                h[k][i + 1] -= pow[k][p[i]];
            } else if (s[i] == '>') {
                p[i + 1]++;
            } else if (s[i] == '<') {
                p[i + 1]--;
            }
            h[k][i + 1] %= MOD[k];
            while (h[k][i + 1] < 0) h[k][i + 1] += MOD[k];
        }
    }

//    for (int i = 0; i <= n; i++) {
//        cout << h[i] << " " << p[i] << "\n";
//    }

    long H[2] = {h[0][n] % MOD[0], h[1][n] % MOD[1]};
    map<pair<long, long>, int> mp;
    long res = 0;
    for (int i = n; i >= 0; i--) {
        long a[2], b[2];
        for (int k = 0; k < 2; k++) {
            a[k] = (h[k][i] * pow[k][MAX + 1]) % MOD[k];
            b[k] = (a[k] + H[k] * pow[k][p[i]]) % MOD[k];
        }
        res += mp[{b[0], b[1]}];
        mp[{a[0], a[1]}]++;
    }
    cout << res << "\n";

    return 0;
}