One-Use Switch

There are $N$ cells in a row. Each cell contains one card whose color is $0$ or $1$.

Switch $i$ lies between cells $i$ and $i+1$ and has operating cost $C_i$.

Every switch can be operated exactly once. Operating a switch $i$ that has not been used performs the following actions in order:

1. If the card colors in cells $i$ and $i+1$ differ immediately before the operation, pay $C_i$.
2. Swap the two cards.
3. Switch $i$ breaks and cannot be operated again.

All $N-1$ switches must be operated exactly once. Find the minimum total cost over all operating orders.

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print the minimum total cost of operating every switch exactly once.

• $1 \leq T \leq 500\,000$.
• $2 \leq N \leq 1\,000\,000$.
• $$ ().