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;

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<ll, ll> ll_ll;

const int MOD0 = 1e9 + 7;
const int MOD1 = 1e9 + 9;

ll INF = LLONG_MAX / 10;

ll pow_mod(ll x, ll n, int M) {
	ll ans = 1;
	for (; n; n>>=1) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
	}
	return ans;
}

int inv_mod(int x, int p) {
	return pow_mod(x, p - 2, p);
}

int main() {
	int N; cin >> N;
	string s; cin >> s;
	int x = 250000; ll h0 = 0, h1 = 0;
	vector<int> X(N + 1); X[0] = x;
	vector<ll> H0(N + 1); H0[0] = h0;
	vector<ll> H1(N + 1); H1[0] = h1;
	rep(i, N) {
		char c = s[i];
		if (c == '+') h0 = (h0 + pow_mod(345678, x, MOD0)) % MOD0;
		if (c == '-') h0 = (h0 - pow_mod(345678, x, MOD0) + MOD0) % MOD0;
		if (c == '+') h1 = (h1 + pow_mod(345678, x, MOD1)) % MOD1;
		if (c == '-') h1 = (h1 - pow_mod(345678, x, MOD1) + MOD1) % MOD1;
		if (c == '>') x++;
		if (c == '<') x--;
		X[i + 1] = x, H0[i + 1] = h0, H1[i + 1] = h1;
	}
	map<ll_ll, int> mp;
	ll ans = 0;
	for (int i = N; i >= 0; i--) {
		int dx = X[i] - X[0];
		ll coef0, coef1;
		if (dx >= 0) coef0 = pow_mod(345678, dx, MOD0);
		else coef0 = inv_mod(pow_mod(345678, -dx, MOD0), MOD0);
		if (dx >= 0) coef1 = pow_mod(345678, dx, MOD1);
		else coef1 = inv_mod(pow_mod(345678, -dx, MOD1), MOD1);
		ll target0 = (H0[i] + H0[N] * coef0) % MOD0;
		ll target1 = (H1[i] + H1[N] * coef1) % MOD1;
		ans += mp[{target0, target1}];
		mp[{H0[i], H1[i]}]++;
	}
	cout << ans << endl;
}