일회용 스위치

일렬로 놓인 $N$개의 칸이 있다. 각 칸에는 색이 $0$ 또는 $1$인 카드가 하나씩 놓여 있다.

칸 $i$와 칸 $i+1$ 사이에는 $i$번 스위치가 있으며, $i$번 스위치의 작동 비용은 $C_i$이다.

각 스위치는 정확히 한 번만 작동시킬 수 있다. 아직 작동시키지 않은 $i$번 스위치를 작동시키면 다음 일이 순서대로 일어난다.

1. 작동 직전 $i$번 칸과 $i+1$번 칸의 카드 색이 서로 다르면 $C_i$의 비용을 지불한다.
2. 두 칸의 카드를 서로 교환한다.
3. $i$번 스위치는 고장 나며 다시 작동시킬 수 없다.

모든 $N-1$개의 스위치를 정확히 한 번씩 작동시켜야 한다. 작동 순서를 자유롭게 정할 때 지불하는 비용 합의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 테스트 케이스마다 모든 스위치를 정확히 한 번씩 작동시킬 때 지불하는 비용 합의 최솟값을 한 줄에 출력한다.

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