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;
typedef unsigned long long ull;
typedef long long giant;
const ull base0=998244353ull;
const ull invr0=996491785301655553ull;
const giant q=1e9+7;
const giant base1=1232351;
const giant invr1=547430890;
const int maxn=2.5e5+3;
const int maxl=5e5+10;
struct H {
	ull x;
	giant y;
	explicit H ():x(0),y(0) {}
	explicit H (ull _x,giant _y):x(_x),y(_y) {}
	inline H& operator = (const int &k) {
		x=k,y=k;
		return *this;
	}
	inline H& operator *= (const H &h) {
		x*=h.x,y=(y*h.y)%q;
		return *this;
	}
	inline H& operator += (const H &h) {
		x+=h.x,y=(y+h.y)%q;
		return *this;
	}
	inline H& operator -= (const H &h) {
		x-=h.x,y=((y-h.y)%q+q)%q;
		return *this;
	}
	inline friend H operator * (H a,const H &b) {
		return a*=b;
	}
	inline friend H operator + (H a,const H &b) {
		return a+=b;
	}
	inline bool operator < (const H &h) const {
		return x!=h.x?(x<h.x):(y<h.y);
	}
} base(base0,base1),invr(invr0,invr1);
namespace num {
	H _mi[maxl],*mi=_mi+maxn;
	void init() {
		mi[0]=1;
		for (int i=1;i<maxn;++i) mi[i]=mi[i-1]*base;
		for (int i=1;i<maxn;++i) mi[-i]=mi[-i+1]*invr;
	}
	int __initer__=(init(),0);
}
int n;
char s[maxn];
map<H,int> mp;
namespace has {
	H val[maxn],cur;
	int pos[maxn];
	void deal(int &p,char c) {
		if (c=='<') --p; else
		if (c=='>') ++p; else
		if (c=='+') cur+=num::mi[p]; else
		if (c=='-') cur-=num::mi[p]; else
		assert(false);
	}
	H work() {
		int p=0;
		for (int i=1;i<=n;++i) {
			deal(p,s[i]);
			val[i]=cur;
			pos[i]=p;
		}
		return cur;
	}
}
int main() {
	scanf("%d%s",&n,s+1);
	H all=has::work();
	giant ans=0;
	for (int i=n;i>=0;--i) {
		H tmp=all*num::mi[has::pos[i]]+has::val[i];
		ans+=mp[tmp];
		++mp[has::val[i]];
	}
	printf("%lld\n",ans);
	return 0;
}