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;

const int pmod = 1e9 + 7;
const int qmod = 1e9 + 9;

struct hash_t {
  int p, q;
  hash_t() {
    
  }
  hash_t(int x, int y) : p(x), q(y) {
  } 
  
  bool operator < (const hash_t &b) const {
    return make_pair(p, q) < make_pair(b.p, b.q);
  }
};

void exgcd(int a, int b, int &x, int &y) {
  if (!b)
    x = 1, y = 0;
  else
    exgcd(b, a % b, y, x), y -= (a / b) * x;
}

int mod_inv(int a, int p) {
  int x, y;
  exgcd(a, p, x, y);
  assert((ll) (x % p + p) % p * a % p == 1);
  return (x % p + p) % p;
}
hash_t operator + (hash_t x, hash_t y) {
  return hash_t((x.p + y.p) % pmod, (x.q + y.q) % qmod);
}
hash_t operator - (hash_t x, hash_t y) {
  return hash_t((x.p + pmod - y.p) % pmod, (x.q + qmod - y.q) % qmod);
} 
hash_t operator * (hash_t x, hash_t y) {
  return hash_t((ll) x.p * y.p % pmod, (ll) x.q * y.q % qmod);
}
hash_t operator / (hash_t x, hash_t y) {
  return hash_t((ll) x.p * mod_inv(y.p, pmod) % pmod, (ll) x.q * mod_inv(y.q, qmod) % qmod);
}

const int MaxN = 250010;

int n; char s[MaxN];
hash_t a[MaxN], b[MaxN];
hash_t x = hash_t(20010403, 20010423);

int main() {
  scanf("%d%s", &n, s + 1);
  a[n + 1] = hash_t(1, 1);
  for (int i = n; i; i--) {
    char c = s[i];
    if (c == '+') {
      a[i] = a[i + 1];
      b[i] = b[i + 1] + hash_t(1, 1);
    }
    if (c == '-') {
      a[i] = a[i + 1];
      b[i] = b[i + 1] - hash_t(1, 1);
    }
    if (c == '>') {
      a[i] = a[i + 1] * x;
      b[i] = b[i + 1] * x;
    } 
    if (c == '<') {
      a[i] = a[i + 1] / x;
      b[i] = b[i + 1] / x;
    }
  } 
  
  map<hash_t, int> h;
  
  ll ans = 0;
  for (int i = n; i; i--) {
    ++h[b[i + 1] / a[i + 1]];
    ans += h[(b[i] - b[1]) / a[i]];
  }
  cout << ans << "\n";
  return 0;
}