You are given an even integer n representing the number of houses arranged in a row, along with a $2$D integer array cost of dimensions n $ imes$ $3$, where cost[i][j] represents the cost to paint house i with color j.

You must paint every house using one of the $3$ colors such that the following conditions are satisfied:

• No two adjacent houses have the same color. That is, house i and house i + 1 must be painted with different colors for all $0 \leq i < n - 1$.

• Houses that are equidistant from the opposite ends cannot have the same color. That is, house i and house $n - 1 - i$ must be painted with different colors for all $0 \leq i < \frac{n}{2}$.

Return the minimum total cost needed to paint all the houses.

Constraints:

• $2 \leq$ n $\leq 10^5$

• n is even.

• cost.length $==$ n

• cost[i].length $== 3$

• $0 \leq$ cost[i][j] $\leq 10^5$

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.