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 ri rd<int>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; --i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++i)
const int O1 = 1004535809;
const int O2 = 998244353;
int O, W, _W;
const int maxN = 250007;
typedef long long LL;

template<class T> inline T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; return f ? x : -x;
}

int pwr(int x, int t) {
	int res = 1;
	for (; t > 0; t >>= 1, x = 1LL * x * x % O)
		if (t & 1) res = 1LL * res * x % O;
	return res;
}

inline int inv(int x) { return pwr(x, O-2); }

int n;
char s[maxN];
int ps[2][maxN], hsh[2][maxN];

void init(int *ps, int *hsh) {
	hsh[0] = 0, ps[0] = 1;
	rep (i, 1, n) {
		if (s[i] == '+') {
			ps[i] = ps[i-1];
			hsh[i] = (hsh[i-1] + ps[i]) % O;
		}
		else if (s[i] == '-') {
			ps[i] = ps[i-1];
			hsh[i] = (hsh[i-1] + O - ps[i]) % O;
		}
		else if (s[i] == '<') {
			ps[i] = 1LL * ps[i-1] * _W % O;
			hsh[i] = hsh[i-1];
		}
		else if (s[i] == '>') {
			ps[i] = 1LL * ps[i-1] * W % O;
			hsh[i] = hsh[i-1];
		}
		else assert(false);
	}
}

void solve() {
	map<pair<int, int>, int> mp;
	LL res = 0;
	rep (i, 0, n) {
		if (i > 0) res += mp[pair<int,int>(hsh[0][i], hsh[1][i])];
		if (i < n) ++mp[pair<int,int>((hsh[0][i] + 1LL * hsh[0][n] * ps[0][i]) % O1, (hsh[1][i] + 1LL * hsh[1][n] * ps[1][i]) % O2)];
	}
	printf("%lld\n", res);
}

int main() {

	n = ri();
	scanf("%s", s+1);

	O = O1, W = 131, _W = inv(W);
	init(ps[0], hsh[0]);
	O = O2, W = 1000003, _W = inv(W);
	init(ps[1], hsh[1]);
	solve();

	return 0;
}