Dance Pad Minimum Energy

A player is playing a four-direction dance pad game. The pad has a center and four directional positions. Number the center as 0, up as 1, left as 2, down as 3, and right as 4.

At first, both feet are on the center position 0. For each instruction, the player must press the required position by moving exactly one of the two feet.

Except for the initial state (0, 0), the two feet may not be on the same position. Therefore, if one foot is already on the next required position, that same foot must press it again.

The energy needed to move a foot is as follows.

• Moving from the center 0 to another position costs 2.
• Pressing the same position again costs 1.
• Moving to an adjacent position costs 3.
• Moving to the opposite position costs 4.

For the sequence 1 2 2 4, moving (0, 0) -> (0, 1) -> (2, 1) -> (2, 1) -> (2, 4) uses 8 energy. It is impossible to satisfy all instructions with less energy.

The input is a sequence of integers representing the instructions. Each instruction is one of 1, 2, 3, and 4, representing up, left, down, and right respectively.

The integer 0 marks the end of the sequence and appears once at the end of the input. The number of instructions excluding the final 0 is at most 100,000.

Print the minimum total energy required to satisfy all instructions.