There is a $3$ lane road of length $n$ that consists of $n + 1$ points labeled from $0$ to $n$. A frog starts at point $0$ on lane $2$ and aims to reach point $n$ on any lane. There may be obstacles along the road.

You are given an integer array obstacles of length $n + 1$, where obstacles[i] indicates that there is an obstacle on lane obstacles[i] at point i. If obstacles[i] is $0$, there are no obstacles at point i. There is at most one obstacle among the $3$ lanes at any given point.

When the frog is on lane lane at point i:

• The frog can move straight ahead to point $i + 1$ on the same lane lane if there is no obstacle on lane lane at point $i + 1$.

• The frog can make a side jump to any other lane at the same point i if the chosen target lane does not have an obstacle at point i.

Return the minimum number of side jumps required for the frog to reach point $n$ starting from lane $2$ at point $0$.

Note: The frog cannot jump to a lane that contains an obstacle at the current point, but it can jump across an obstructed lane.

Constraints:

• obstacles.length $= n + 1$

• $1 \leq n \leq 5 imes 10^5$

• $0 \leq$ obstacles[i] $\leq 3$

• obstacles[0] $= 0$ and obstacles[n] $= 0$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.