만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

고양이

면접 대비

시간 제한1초메모리 제한16 MB

요약
고양이, 개, 사자가 한 줄로 늘어서 있을 때, 고양이와 개가 서로 이웃하지 않도록 줄을 바꾸는 최소 이동 횟수를 구한다.
난이도

보통10점 중 6점

유형
그리디, 동적 계획법, 배열, 누적 합
정답자
아직 제출이 없습니다

문제

알렉스는 반려동물 NN마리를 한 줄로 세워 두었다. 동물은 고양이, 개, 사자 세 종류다. 고양이와 개는 사이가 나쁘지만, 사자는 고양이와도 개와도 잘 지낸다.

알렉스는 이동을 한 번 할 때마다 동물 한 마리를 골라 줄의 다른 자리로 옮길 수 있다.

고양이와 개가 서로 이웃하지 않도록 줄을 바꾸려고 한다. 필요한 최소 이동 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 서로 독립인 테스트 케이스의 수 TT가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에 정수 NN이 주어진다. 둘째 줄에는 줄에 선 순서대로 동물 NN마리의 종류가 공백으로 구분되어 주어진다. 고양이는 0, 개는 1, 사자는 2로 나타낸다.

출력

각 테스트 케이스마다 한 줄씩 출력한다. 고양이와 개가 이웃하지 않도록 배치할 방법이 없으면 -1을 출력하고, 그렇지 않으면 필요한 최소 이동 횟수를 출력한다.

제한

  • 1≤T≤5001 \le T \le 500
  • 1≤N≤50001 \le N \le 5000
  • 한 입력에 주어지는 모든 NN의 합은 5000 이하다.

힌트

첫 번째 예제의 첫 테스트에서는 개 두 마리를 줄의 끝으로 옮긴다. 두 번째 테스트에서는 마지막 사자를 첫 번째 개 앞으로 옮긴다.

예제3

  1. 예제 1

    입력
    2
5
0 1 0 1 2
9
0 0 0 1 1 2 0 0 2
    예상 출력
    2
1

  2. 예제 2

    입력
    5
1
0
1
2
2
0 1
3
1 1 1
4
0 2 1 2
    예상 출력
    0
0
-1
0
0

  3. 예제 3

    입력
    4
4
0 1 0 2
4
1 0 1 2
4
2 0 1 0
4
2 1 0 1
    예상 출력
    1
1
1
1