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;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll extgcd(ll a, ll b, ll &x, ll &y) { ll d; return b == 0 ? (x = 1, y = 0, a) : (d = extgcd(b, a % b, y, x), y -= a / b * x, d); }
ll modinv(ll a, ll mod = 1e9 + 7) { ll x = 0, y = 0; extgcd(a, mod, x, y); return (x + mod) % mod; }
ll modpow(ll a, ll b, ll mod = 1e9 + 7) { ll r = 1; a %= mod; while(b) { if(b & 1) r = r * a % mod; a = a * a % mod; b >>= 1; } return r; }

const int N = 250000 + 10;
const ll mod = 1e9 + 7;
vector<ll> gen{114514, 1919};
vector<map<ll, int>> Bex(gen.size());
int n;
string s;
int ms[N];
ll calc(int i, int c, ll x) {
  if(i == 0) {
    // A
    if(c <= 1) return 1;
    if(c == 2) return modinv(x, mod);
    return x;
  } else {
    if(c == 0) return 1;
    if(c == 1) return -1;
    return 0;
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> s;
  vector<vector<ll>> A(gen.size(), vector<ll>(n+2)), B = A;
  for(int i = 0; i < n; i++) {
    if(s[i] == '+') ms[i] = 0;
    else if(s[i] == '-') ms[i] = 1;
    else if(s[i] == '>') ms[i] = 2;
    else ms[i] = 3;
  }
  for(int k = 0; k < gen.size(); k++) {
    gen[k] = ((gen[k] % mod + mod) % mod);
    ll x = gen[k];
    A[k][1] = 1;
    B[k][1] = 0;
    for(int i = 0; i < n; i++) {
      A[k][i+2] = A[k][i+1] * calc(0, ms[i], x) % mod;
      B[k][i+2] = A[k][i+1] * calc(1, ms[i], x) % mod + B[k][i+1];
      B[k][i+2] = ((B[k][i+2] % mod + mod) % mod);
      Bex[k][B[k][i+2]]++;
    }
  }
  ll ans = 0;
  for(int i = 0; i < n; i++) {
    ll mi = 1e18;
    for(int k = 0; k < gen.size(); k++) {
      ll c = A[k][i+1] * B[k][n+1] % mod;
      c += B[k][i+1];
      c %= mod;
      ll cnt = Bex[k][c];
      mi = min(mi, cnt);
      // if(cnt != mi) mi = min(mi, cnt);
      // else break;
    }
    for(int k = 0; k < gen.size(); k++) Bex[k][B[k][i+2]]--;
    ans += mi;
  }
  cout << ans << endl;
}