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 For(i,l,r) for(int i = (l),i##end = (r);i <= i##end;i++)
#define Fordown(i,r,l) for(int i = (r),i##end = (l);i >= i##end;i--)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

template <typename T> inline bool chkmin(T &x,T y) { return y < x ? x = y,1 : 0; }
template <typename T> inline bool chkmax(T &x,T y) { return x < y ? x = y,1 : 0; }

const int INF = 0x3f3f3f3f;
const int N = 250000 + 10,Bs = 19260817;

int Pos[N];
ull Pw[N << 1],Val[N];
char str[N];

unordered_map <ull,int> Map;

inline int read() {
	int x = 0,flag = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')flag = -1,ch = getchar();
	while(isdigit(ch))x = (x << 3) + (x << 1) + (ch - '0'),ch = getchar();
	return x * flag;
}

int main() {

	int n = read(),Lim = (n << 1) + 10;
	scanf("%s",str + 1);
	Pw[0] = 1;
	For(i,1,Lim) Pw[i] = Pw[i - 1] * Bs;
	int pos = n + 5;ull Sum = 0;
	For(i,1,n) {
		if(str[i] == '>') pos++;
		if(str[i] == '<') pos--;
		if(str[i] == '+') Sum += Pw[pos];
		if(str[i] == '-') Sum -= Pw[pos];
		Pos[i] = pos,Val[i] = Sum;
	}

	Map[Val[n] * Pw[n + 5]]++;
	ll ans = 0;
	Fordown(i,n - 1,1) {
		ull val = Val[n] * Pw[Pos[i]] + Val[i] * Pw[n + 5];
		ans += Map[val];
		Map[Val[i] * Pw[n + 5]]++;
	}

	For(i,1,n) if(Val[i] == Val[n]) ans++;

	printf("%lld\n",ans);

	return 0;
}