题目描述

すけぬ君建造了一栋有 $N$ 层的楼房。楼内有一部电梯，可以在所有楼层停靠。

すけぬ君在每一层都装了上下方向的按钮，但由于疏忽，每一层只能装上行或下行其中一种按钮。因此，从任意一层只能往上或往下，其方向由按钮决定。若 $S_i$ 为 U，表示第 $i$ 层只有上行按钮，只能向上移动；若为 D，则只有下行按钮，只能向下移动。

住户们有时需要从某一层前往另一层。在按钮限制下，他们只能选择允许的方向，如果无法直接到达目标层，则需要借道其它楼层。请你计算，对于楼内所有的有序对 $(i, j)$，即从第 $i$ 层到第 $j$ 层，住户最少需要乘坐多少次电梯，将这些最小乘坐次数全部加和，输出总和。

输入格式

输入为一行，格式如下：

$S_1S_2\dots S_{|S|}$

输出格式

请输出所有有序对 $(i, j)$（$1 \leq i, j \leq N$）中，从第 $i$ 层到第 $j$ 层所需最少乘坐电梯次数之和。

样例 1

输入

UUD

输出

7

样例 2

输入

UUDUUDUD

输出

77

说明/提示

限制

• $2\leq |S| \leq 10^5$
• $S_i$ 只为 U 或 D
• 第 $1$ 层必为 U
• 第 $N$ 层必为 D

样例解释

从第 $1$ 层到第 $2$ 层，只需乘坐电梯 $1$ 次即可，到第 $3$ 层同样 $1$ 次。
从第 $2$ 层到第 $1$ 层，需要 $2$ 次。到第 $3$ 层需要 $1$ 次。
从第 $3$ 层到第 $1$ 层需要 $1$ 次，到第 $2$ 层需要 $1$ 次。
以上所有情况的最小乘坐次数之和为 $7$，所以输出 $7$。

由 ChatGPT 5 翻译