F - Eating Symbols Hard

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1200

問題文

高橋君は,いつも頭の中に,長さ 2 \times 10^9 + 1 の整数列 A = (A_{-10^9}, A_{-10^9 + 1}, ..., A_{10^9 - 1}, A_{10^9}) と,整数 P を思い浮かべています.

はじめ,高橋君が思い浮かべている整数列 A のすべての要素は 0 です. また,整数 P の値は 0 です.

高橋君は,+, -, >, < の記号を食べると,それぞれ次のように思い浮かべている整数列 A,整数 P が変化します:

  • + を食べた場合,A_P の値が 1 大きくなる.
  • - を食べた場合,A_P の値が 1 小さくなる.
  • > を食べた場合,P の値が 1 大きくなる.
  • < を食べた場合,P の値が 1 小さくなる.

高橋君は,長さ N の文字列 S を持っています.S の各文字は +, -, >, < の記号のいずれかです. 高橋君は,1 \leq i \leq j \leq N なる整数の組 (i, j) を選んで,Si, i+1, ..., j 文字目の記号をこの順に食べました. 高橋君が記号を食べ終わった後,高橋君が思い浮かべている整数列 A は,高橋君が S のすべての記号を 1 文字目から順に食べた場合と等しくなったといいます. このような (i, j) として考えられるものは何通りあるか求めてください.

制約

  • 1 \leq N \leq 250000
  • |S| = N
  • S の各文字は +, -, >, < のいずれか

入力

入力は以下の形式で標準入力から与えられる.

N
S

出力

答えを出力せよ.


入力例 1

5
+>+<-

出力例 1

3

高橋君が S のすべての記号を食べた場合,A_1 = 1 で,A の他の要素はすべて 0 になります. A がこれと等しくなるような (i, j) は次の通りです:

  • (1, 5)
  • (2, 3)
  • (2, 4)

入力例 2

5
+>+-<

出力例 2

5

高橋君が S のすべての記号を食べた場合と P が異なっていてもかまわないことに注意してください.


入力例 3

48
-+><<><><><>>>+-<<>->>><<><<-+<>><+<<>+><-+->><<

出力例 3

475

Score : 1200 points

Problem Statement

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.


Sample Input 1

5
+>+<-

Sample Output 1

3

If Takahashi eats all the symbols in S, A_1 = 1 and all other elements would be 0. The pairs (i, j) that leads to the same sequence A are as follows:

  • (1, 5)
  • (2, 3)
  • (2, 4)

Sample Input 2

5
+>+-<

Sample Output 2

5

Note that the value of P may be different from the value when Takahashi eats all the symbols in S.


Sample Input 3

48
-+><<><><><>>>+-<<>->>><<><<-+<>><+<<>+><-+->><<

Sample Output 3

475