F - Eating Symbols Hard Editorial /

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) を選んで，S の i, 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