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>
#define eb emplace_back
using namespace std;
typedef long long ll;
mt19937 rdf(time(0));
int rd(int s, int e) { return rdf() % (e-s+1) + s; }

const int MOD = 1000009399;
const int MAXN = 250055;

ll pw(ll n, ll k) {
	ll r = 1; for(; k; k >>= 1) {
		if(k & 1) r = r * n % MOD;
		n = n * n % MOD;
	}
	return r;
}
ll inv(ll n) { return pw(n, MOD-2); }

struct NOD {
	NOD(int a = 1, int b = 0) : a(a), b(b) {}
	int a, b;

	int operator () (int t) const {
		return (ll(a)*t + b) % MOD;
	}
	NOD operator * (const NOD &t) const {
		return NOD(ll(a)*t.a % MOD, (ll(a)*t.b + b) % MOD);
	}
} nod[6][MAXN], gma[6][4];

map<vector<int>, int> MP;

int X[6], RX[6], C[6];

char A[MAXN];

ll Ans;
int N;

int f(char c) {
	if('+' == c) return 0;
	if('-' == c) return 1;
	return '>' == c ? 2 : 3;
}

int main() {
	scanf("%d %s", &N, A+1);

	for(int i = 0; i < 6; i++) {
		X[i] = rd(40148, 957370123);
		RX[i] = inv(X[i]);

		gma[i][0] = NOD(1, MOD-1);
		gma[i][1] = NOD(1, 1);
		gma[i][2] = NOD(RX[i], 0);
		gma[i][3] = NOD(X[i], 0);

		for(int j = N; j; j--) {
			nod[i][j] = nod[i][j+1] * gma[i][f(A[j])];
			C[i] = gma[i][f(A[j])^1](C[i]);
		}
	}

	for(int i = N; i; i--) {
		vector<int> V(6);
		for(int j = 0; j < 6; j++) V[j] = nod[j][i+1](0);
		MP[V]++;
		for(int j = 0; j < 6; j++) V[j] = nod[j][i](C[j]);
		auto it = MP.find(V);
		if(MP.end() != it) Ans += it -> second;
	}

	cout << Ans << endl;
	return 0;
}