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 <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
#define fst first
#define snd second
using ll = long long;
using I = pair<int, int>;

ll mod_pow(ll x, ll e, ll M) {
  ll v = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) {
      v = v * x % M;
    }
    x = x * x % M;
  }
  return v;
}

ll inverse(ll x, ll M) { return mod_pow(x, M - 2, M); }

int main() {
  int N;
  string S;
  while (cin >> N >> S) {
    ll base = 9973ll;
    vector<ll> mods = {ll(1e9 + 7), ll(1e9 + 9)};
    vector<vector<ll>> pows(mods.size(), vector<ll>(2 * N + 1));
    for (int i = 0; i < mods.size(); i++) {
      for (int e = -N; e <= N; e++) {
        ll p = mod_pow(base, (ll)abs(-e), mods[i]);
        if (e < 0) {
          p = inverse(p, mods[i]);
        }
        pows[i][e + N] = p;
      }
    }
    vector<int> P(N + 1, 0);
    vector<vector<ll>> H(N + 1, vector<ll>(mods.size(), 0));
    for (int i = 0; i < N; i++) {
      P[i + 1] = P[i];
      H[i + 1] = H[i];
      if (S[i] == '<') --P[i + 1];
      if (S[i] == '>') ++P[i + 1];
      if (S[i] == '+') {
        for (int j = 0; j < mods.size(); j++)
          H[i + 1][j] = (H[i + 1][j] + pows[j][P[i + 1] + N]) % mods[j];
      }
      if (S[i] == '-') {
        for (int j = 0; j < mods.size(); j++)
          H[i + 1][j] =
              (H[i + 1][j] - pows[j][P[i + 1] + N] + mods[j]) % mods[j];
      }
    }
    vector<ll> A = H[N];
    map<vector<ll>, int> mp;
    ll res = 0;
    for (int i = N - 1; i >= 0; i--) {
      ++mp[H[i + 1]];
      vector<ll> Q(mods.size(), 0);
      for (int j = 0; j < mods.size(); j++)
        Q[j] = ((A[j] * pows[j][P[i] + N] % mods[j]) + H[i][j]) % mods[j];
      res += mp[Q];
    }
    cout << res << endl;
  }
  return 0;
}