# A. Robot Sequence

time limit per test：2 seconds

memory limit per test：256 megabytes

input：standard input

output：standard output

Calvin the robot lies in an infinite rectangular grid. Calvin's source code contains a list of n commands, each either 'U', 'R', 'D', or 'L' — instructions to move a single square up, right, down, or left, respectively. How many ways can Calvin execute a non-empty contiguous substrings of commands and return to the same square he starts in? Two substrings are considered different if they have different starting or ending indices.

Input

The first line of the input contains a single positive integer, n (1 ≤ n ≤ 200) — the number of commands.

The next line contains n characters, each either 'U', 'R', 'D', or 'L' — Calvin's source code.

Output

Print a single integer — the number of contiguous substrings that Calvin can execute and return to his starting square.

Examples

Input

6
URLLDR

Output

2

Input

4
DLUU

Output

0

Input

7
RLRLRLR

Output

12

Note

In the first case, the entire source code works, as well as the "RL" substring in the second and third characters.

Note that, in the third case, the substring "LR" appears three times, and is therefore counted three times to the total result.

1 #include <bits/stdc++.h>
2 using namespace std;
4 {
5     int x=0,f=1;
6     char ch=getchar();
7     while(ch<'0'||ch>'9')
8     {
9         if(ch='-')
10             f=-1;
11         ch=getchar();
12     }
13     while(ch>='0'&&ch<='9')
14     {
15         x=x*10+ch-'0';
16         ch=getchar();
17     }
18     return x*f;
19 }
20 int n;
21 char s[255];
22 int main()
23 {
25     cin>>s;
26     int e=0;
27     for(int i=0;i<n;i++)
28     {
29         int a=0,b=0,c=0,d=0;
30         for(int j=i;j<n;j++)
31         {
32             if(s[j]=='U')
33                 a++;
34             if(s[j]=='D')
35                 b++;
36             if(s[j]=='L')
37                 c++;
38             if(s[j]=='R')
39                 d++;
40             if(a==b&&c==d)
41                 e++;
42         }
43     }
44     cout<<e<<endl;
45     return 0;
46 }

795 篇文章64 人订阅

0 条评论

## 相关文章

### Scala Macros － 元编程 Metaprogramming with Def Macros

Scala Macros对scala函数库编程人员来说是一项不可或缺的编程工具，可以通过它来解决一些用普通编程或者类层次编程（type level pr...

32090

140100

21420

15030

10810

94810

### 回文自动机、AC自动机和后缀自动机介绍（1）

我们还从一个非常经典的题目出发，最长公共子串问题。给定两个字符串S和T，求S和T的最长公共子串的长度。比如abcdefg和abacabca的最长公共子串是ab...

32330

27650

29510

27580