C. Santa Claus and Robot

Codeforces

IDCF752C

Time2000ms

Memory256MB

Difficulty—

greedyshortest paths

Santa Claus has Robot which lives on the infinite grid and can move **along its lines**. He can also, having a sequence of _m_ points _p_1, _p_2, ..., _p__m_ with integer coordinates, do the following: denote its initial location by _p_0. First, the robot will move from _p_0 to _p_1 along one of the shortest paths between them (please notice that since the robot moves only along the grid lines, there can be several shortest paths). Then, after it reaches _p_1, it'll move to _p_2, again, choosing one of the shortest ways, then to _p_3, and so on, until he has visited all points in the given order. Some of the points in the sequence may coincide, in that case Robot will visit that point several times according to the sequence order. While Santa was away, someone gave a sequence of points to Robot. This sequence is now lost, but Robot saved the protocol of its unit movements. Please, find the minimum possible length of the sequence. ## Input The first line of input contains the only positive integer _n_ (1 ≤ _n_ ≤ 2·105) which equals the number of unit segments the robot traveled. The second line contains the movements protocol, which consists of _n_ letters, each being equal either _L_, or _R_, or _U_, or _D_. _k_\-th letter stands for the direction which Robot traveled the _k_\-th unit segment in: _L_ means that it moved to the left, _R_ — to the right, _U_ — to the top and _D_ — to the bottom. Have a look at the illustrations for better explanation. ## Output The only line of input should contain the minimum possible length of the sequence. [samples] ## Note The illustrations to the first three tests are given below. ![image](https://espresso.codeforces.com/832fb8f97a482be815e0f87edde26c9791a0d330.png) ![image](https://espresso.codeforces.com/119a8ba68772b2c2bf76f2acdc58027f6c5cde1f.png) ![image](https://espresso.codeforces.com/c7b4534f24cbad48148bcba24bc44f37bf7a2dbf.png) The last example illustrates that each point in the sequence should be counted as many times as it is presented in the sequence.

Samples

Input #1

4
RURD

Output #1

Input #2

6
RRULDD

Output #2

Input #3

26
RRRULURURUULULLLDLDDRDRDLD

Output #3

Input #4

3
RLL

Output #4

Input #5

4
LRLR

Output #5

API Response (JSON)

{
  "problem": {
    "name": "C. Santa Claus and Robot",
    "description": {
      "content": "Santa Claus has Robot which lives on the infinite grid and can move **along its lines**. He can also, having a sequence of _m_ points _p_1, _p_2, ..., _p__m_ with integer coordinates, do the following",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF752C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Santa Claus has Robot which lives on the infinite grid and can move **along its lines**. He can also, having a sequence of _m_ points _p_1, _p_2, ..., _p__m_ with integer coordinates, do the following...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments