问题2739--无

2739: 无

时间限制: 1 Sec  内存限制: 128 MB
提交: 74  解决: 33
[状态] [讨论版] [提交] [命题人:]
题目描述
给一个序列a,包含n个整数,a的序号由1到n。你可以选择一个整数x(只能选一次,且x在序列a中),你可以进行一次或者多次下列操作:
你可以选择第r个到第l个连续的数字(1<=r<=l<=n),变成x,但有一个前提,第r到第l个数字中不能有等于x的数字。
求最少多少次操作,可以使整个序列a中的数都变成你所选的x。
例如n=6,a={1,3,2,4,1,2},你可以选择x=1,进行第一次操作,r=2,l=4,所以此时a={1,1,1,1,1,2}。再次进行操作,r=6,l=6,此时序列a={1,1,1,1,1,1}。
输入
输入第1行为一个整数t(1≤n≤10),代表测试的组数。
下面有t组测试数据每组有两行
第一行包括一个整数n,表示序列a有n个整数(1<=n<=200000)
第二行包括n个整数,a1,a2,a3,…,an (1<=ai<=n)
输出
输出最小的操作次数,使序列a中的整数全变为x
样例输入 Copy
5
3
1 1 1
5
1 2 3 4 5
5
1 2 3 2 1
7
1 2 3 1 2 3 1
11
2 2 1 2 3 2 1 2 3 1 2
样例输出 Copy
0
1
1
2
3
来源/分类