题目描述

为了避免餐厅（不是老八餐厅哟）过分拥挤，FJ 要求奶牛们分 \(2\) 批就餐：所有第 \(2\) 批就餐的奶牛排在队尾，第 \(1\) 批就餐的奶牛则占据队首。第 \(i\) 头奶牛有一张标明她用餐批次 \(D_i\) 的卡片。虽然所有头奶牛排成了很整齐的队伍，但她们卡片上的号码是完全杂乱无章的。FJ 找到了一种简单些的方法：奶牛们不动，他沿着队伍从头到尾走一遍，把那些他认为排错队的奶牛卡片上的编号改掉，最终得到一个他想要的每个组中的奶牛都站在一起的队列，例如 \(112222\) 或 \(111122\)。有的时候，FJ 会把整个队列弄得只有 \(1\) 组奶牛（比方说，\(1111\) 或 \(222\)）。他想知道，如果他想达到目的，那么他最少得改多少头奶牛卡片上的编号。所有奶牛在 FJ 改卡片编号的时候，都不会挪位置。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示测试数据组数；每组数据的第一行为正整数 \(n(≤30,000)\)，表示奶牛个数；接下来一行，为 \(n\) 个正整数 \(D_i(D_i=1\) 或 \(2\))，分别表示为每头奶牛的用餐批次。

输出格式

对于每组数据，输出 FJ 最少要改编号的个数。

样例1

样例输入1

2
7
2 1 1 1 2 2 1
5
2 2 1 1 1

样例输出1

2
2

样例解释

样例 \(1\) 中，把第 \(1\) 个 \(2\) 改成 \(1\)，最后 \(1\) 个 \(1\) 改成 \(2\)；样例 \(2\) 中，把前 \(2\) 个 \(2\) 均改成 \(1\)，改动次数均为 \(2\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T3\)

文件IO

freopen("dining.in","r",stdin);
freopen("dining.out","w",stdout);