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 <iostream>
#include <string>
#include <map>
#define hash __hash

using namespace std;

typedef long long ll;
typedef unsigned long long hash;

const hash BASE = 2340298430918231;
const hash INVBASE = 353531932664012135;

const int MAX_N = 3e5 + 5;

hash _basepow [2 * MAX_N];
hash& basepow (int idx) {
  return _basepow[idx + MAX_N];
}

hash hash_at [MAX_N];
int start_at [MAX_N];

int main () {
  ios::sync_with_stdio(false);

  basepow(0) = 1;
  for (int i = 1; i < MAX_N; i++) {
    basepow(i) = basepow(i - 1) * BASE;
  }
  for (int i = -1; i > -MAX_N; i--) {
    basepow(i) = basepow(i + 1) * INVBASE;
  }
  
  int n;
  cin >> n;
  
  string str;
  cin >> str;

  hash cur = 0;
  hash pos = 1;
  int start = 0;
  for (int i = 0; i < (int) str.size(); i++) {
    char c = str[i];
    if (c == '+') cur += pos;
    if (c == '-') cur -= pos;
    if (c == '>') {
      pos *= BASE;
      start++;
    }
    if (c == '<') {
      pos *= INVBASE;
      start--;
    }

    hash_at[i + 1] = cur;
    start_at[i + 1] = start;
  }
  
  map<hash, int> cnt;
  ll ans = 0;
  for (int i = (int) str.size(); i >= 0; i--) {
    hash target = cur * basepow(start_at[i]) + hash_at[i];
    if (cnt.count(target) != 0) {
      ans += cnt[target];
    }

    if (cnt.count(hash_at[i]) == 0) {
      cnt[hash_at[i]] = 0;
    }
    cnt[hash_at[i]]++;
  }

  cout << ans << endl;
}