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 N = 250033, mod1 = 1000000007, mod2 = 1000109107;
int qpow(int b, int p, int m) {
  int r = 1;
  for (; p; p >>= 1, b = (ll) b * b % m) if (p & 1) r = (ll) r * b % m;
  return r;
}
struct data {
  int x, y;
  data(int x = 0, int y = 0) : x(x), y(y) {}
  data operator + (const data &d) const {return data((x + d.x) % mod1, (y + d.y) % mod2);}
  data operator - (const data &d) const {return data((x + mod1 - d.x) % mod1, (y + mod2 - d.y) % mod2);};
  data operator * (const data &d) const {return data((ll) x * d.x % mod1, (ll) y * d.y % mod2);}
  data operator / (const data &d) const {return data((ll) x * qpow(d.x, mod1 - 2, mod1) % mod1, (ll) y * qpow(d.y, mod2 - 2, mod2) % mod2);}
  ll get() {return (ll) x << 30 | y;}
};
data X(159623, 102647), f[N], g[N], h[N], k(1, 1), b;
int n;
ll ans;
char s[N];
map<ll, int> mp;

int main() {
  scanf("%d%s", &n, s + 1);
  for (int i = 1; i <= n; i++) {
    if (s[i] == '+') b = b + k;
    if (s[i] == '-') b = b - k;
    if (s[i] == '>') k = k * X;
    if (s[i] == '<') k = k / X;
    f[i] = b;
  }
  g[0] = k = data(1, 1), h[0] = b = data(0, 0);
  for (int i = 1; i <= n; i++) {
    if (s[i] == '+') b = b - data(1, 1);
    if (s[i] == '-') b = b + data(1, 1);
    if (s[i] == '>') k = k / X, b = b / X;
    if (s[i] == '<') k = k * X, b = b * X;
    g[i] = k, h[i] = b;
  }
  for (int i = n; i >= 0; i--) {
    data t = (f[n] - h[i]) / g[i];
    ans += mp[t.get()];
    mp[f[i].get()]++;
  }
  printf("%lld\n", ans);
}