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>
typedef long ll;
const int maxn = 250002;
char buf[maxn];
int n,sum,s[maxn];
inline void reduce(int & x,const int & mod){ x += x >> 31 & mod; }
inline int pow(int a,int b,const int & mod,int ret = 1){
	for(b = b % (mod - 1) + mod - 1;b;b>>=1,a=ll(a) * a % mod)if(b & 1)
		ret = ll(ret) * a % mod;
	return ret;
}
constexpr int m0 = 1192230913,b0 = 233333;
constexpr int m1 = 1085276161,b1 = 2333333;
struct Int{
	int a0,a1;
	inline Int(int x0 = 0,int x1 = 0){ a0 = x0,a1 = x1; }
	inline void add(){ reduce(a0 += b0 - m0,m0); reduce(a1 += b1 - m1,m1); }
	inline void dec(){ reduce(a0 -= b0,m0); reduce(a1 -= b1,m1); }
	inline void mul(int cnt){ a0 = pow(b0,cnt,m0,a0); a1 = pow(b1,cnt,m1,a1); }
	inline bool operator < (const Int & b) const { return * (ll*) this < * (ll*) & b; }
} a[maxn], b[maxn];

int main()
{
	std::ios::sync_with_stdio(false),std::cin.tie(0);
	std::cin >> n >> buf + 1;
	for(int i = 1;i <= n;++i){
		a[i] = a[i - 1];
		if(buf[i] == '+') a[i].add();
		if(buf[i] == '-') a[i].dec();
		if(buf[i] == '>') a[i].mul(1),--sum;
		if(buf[i] == '<') a[i].mul(-1),++sum;
		s[i] = sum;
		(b[i] = a[i]).mul(sum);
	}
	ll ans = 0;
	std::map<Int,int> map;
	for(int i = n;i >= 0;--i){
		Int x = b[n]; x.mul(s[i]);
		ans += map[Int(((ll)b[i].a0 + x.a0) % m0,(b[i].a1 + x.a1) % m1)];
		++map[b[i]];
	}
	std::cout << ans << '\n';
}