Counting Valleys

You are given a string of characters where each character is either 'U' (up) or 'D' (down). This string represents a series of steps taken from sea level. A valley is defined as a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level. Your task is to count the number of valleys traversed during the hike.

Details:

• Each 'U' increments the current level by 1.
• Each 'D' decrements the current level by 1.
• A valley is counted when you come up to sea level from below (i.e. from a negative level).

It is guaranteed that the hike always starts and ends at sea level.

The formula for updating the level is given by the following recurrence:

\( level_{i} = level_{i-1} + \begin{cases} +1, & \text{if step } i \text{ is } U \\ -1, & \text{if step } i \text{ is } D \end{cases} \)

inputFormat

The input consists of a single line containing a non-empty string of characters, each of which is either 'U' or 'D', representing the steps taken during the hike.

outputFormat

Output a single integer indicating the number of valleys traversed.

DU

1