题目描述

すけぬ君は、$N$ 階建てのビルを建てました。ビルにはエレベーターが $1$ 基あり、すべての階に止まります。

すけぬ君は、各階に上下の方向ボタンを設置しましたが、うっかりしていたため、どの階にも上向きか下向きの片方のボタンしかありません。 そのため、どの階からも上か下のどちらかにしか進むことができません。 $S_i$ が U のとき $i$ 階には上向きのボタンしかなく、上にしか進めないことを、D のとき下向きのボタンしかなく、 下にしか進めないことを表します。

ある階から目的の階へと移動したい住民は、仕方がないので必要があれば他の階を経由して目的の階へと向かうことにしました。 全ての階の順序対 $(i,j)$ についての、$i$ 階から $j$ 階へ行くときのエレベーターに乗る回数の最小値の合計を求めてください。

输入格式

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

$S_1S_2...S_{|S|}$

输出格式

全ての階の順序対 $(i,j)$ についての、$i$ 階から $j$ 階へ行くときのエレベーターに乗る回数の最小値の合計を出力せよ。

题目大意

给定一个长度为 $n(n≤10^5)$ 的字符串，每个字符为$U$ 或 $D$。第 $i$ 位上的字符表示，从第 $i$ 楼乘电梯出发只能向上($U$)或向下($D$)。

定义$f(u,v)$表示从第 $u$ 楼到第 $v$ 楼至少需要乘电梯的次数。

求$\sum_{i=1}^n \sum_{j\ne i}^n f(i,j)$。

UUD

7

UUDUUDUD

77

提示

制約

• $2\ ≦\ |S|\ ≦\ 10^5$
• $S_i$ は U または D である
• $S_1$ は U である
• $S_{|S|}$ は D である

Sample Explanation 1

$1$ 階から $2$ 階までは、$1$ 回エレベーターに乗れば行くことができます。 $1$ 階から $3$ 階までは、$1$ 回エレベーターに乗れば行くことができます。 $2$ 階から $1$ 階までは、$2$ 回エレベーターに乗れば行くことができます。 $2$ 階から $3$ 階までは、$1$ 回エレベーターに乗れば行くことができます。 $3$ 階から $1$ 階までは、$1$ 回エレベーターに乗れば行くことができます。 $3$ 階から $2$ 階までは、$1$ 回エレベーターに乗れば行くことができます。 これらの合計は $7$ なので、$7$ を出力します。