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;
constexpr int P = 998244353;
constexpr int BASE[] {19260817, 20030912, 19491001, 114514, 1919810};
constexpr int INV_BASE[] {494863259, 434508607, 157440299, 137043501, 595887626};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin >> n >> s;
    vector<vector<int>> a(n + 1);
    vector<vector<int>> b(n + 1);
    for (int i = 0; i <= n; ++i) {
        a[i].resize(5);
        b[i].resize(5);
    }
    for (int j = 0; j < 5; ++j) {
        int c = 0;
        for (int i = n - 1; i >= 0; --i) {
            switch (s[i]) {
                case '+' :
                    c = (c + 1) % P;
                    break;
                case '-':
                    c = (c - 1 + P) % P;
                    break;
                case '>':
                    c = 1LL * c * BASE[j] % P;
                    break;
                case '<':
                    c = 1LL * c * INV_BASE[j] % P;
                    break;
            }
        }
        auto calc = [&](vector<vector<int>> &a, int c) {
            a[n][j] = c;
            int k = 1, b = 0;
            for (int i = n - 1; i >= 0; --i) {
                switch (s[i]) {
                    case '+' :
                        b = (b - k + P) % P;
                        break;
                    case '-':
                        b = (b + k) % P;
                        break;
                    case '>':
                        k = 1LL * k * INV_BASE[j] % P;
                        break;
                    case '<':
                        k = 1LL * k * BASE[j] % P;
                        break;
                }
                a[i][j] = (1LL * k * c + b) % P;
            }
        };
        calc(a, c);
        calc(b, 0);
    }
    LL ans = 0;
    map<vector<int>, int> cnt;
    for (int i = 0; i <= n; ++i) {
        ans += cnt[b[i]];
        ++cnt[a[i]];
    }
    cout << ans << endl;
    return 0;
}