class Solution {
 public:
  int minSideJumps(vector<int>& obstacles) {
    constexpr int kInf = 1e6;

    // dp[i] := min jump to reach lane i
    vector<int> dp{kInf, 1, 0, 1};

    for (const int obstacle : obstacles) {
      if (obstacle > 0)
        dp[obstacle] = kInf;
      for (int i = 1; i <= 3; ++i)  // current
        if (i != obstacle)
          for (int j = 1; j <= 3; ++j)  // prev
            dp[i] = min({dp[i], dp[j] + (i == j ? 0 : 1)});
    }

    return *min_element(begin(dp), end(dp));
  }
};

class Solution {
  public int minSideJumps(int[] obstacles) {
    final int kInf = (int) 1e6;

    // dp[i] := min jump to reach lane i
    int[] dp = {kInf, 1, 0, 1};

    for (final int obstacle : obstacles) {
      if (obstacle > 0)
        dp[obstacle] = kInf;
      for (int i = 1; i <= 3; ++i) // current
        if (i != obstacle)
          for (int j = 1; j <= 3; ++j) // prev
            dp[i] = Math.min(dp[i], dp[j] + (i == j ? 0 : 1));
    }

    return Arrays.stream(dp).min().getAsInt();
  }
}

class Solution:
  def minSideJumps(self, obstacles: List[int]) -> int:
    kInf = 1e6

    # dp[i] := min jump to reach lane i
    dp = [kInf, 1, 0, 1]

    for obstacle in obstacles:
      print(dp)
      if obstacle > 0:
        dp[obstacle] = kInf
      for i in range(1, 4):  # current
        if i != obstacle:
          for j in range(1, 4):  # prev
            dp[i] = min(dp[i], dp[j] + (0 if i == j else 1))

    return min(dp)