#E. [CZOJ 一周一测 R15 E] 天空之梦

    传统题 4000ms 256MiB

[CZOJ 一周一测 R15 E] 天空之梦

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

注意:由于 CZOJ 评测机较慢,请使用较快的输入输出,并在提交时打开 O2 优化。

Description

那是我向往的天空之梦。

空中飘着我所仰望的 nn 个气球,他们排成了一排。

每个气球有一个代表颜色的整数编号 ci[1,n]c_i\in[1,n],相同颜色的编号相同。

每次操作可以选取一个区间 [l,r][l,r],满足 cl=cl+1==crc_l=c_{l+1}=\cdots=c_r,并将它们同时改为任意一个颜色 k[1,n]k\in[1,n]

求使得所有气球颜色相同的最少操作次数。

Format

Input

第一行包含一个整数 tt 表示测试数据的数量。

对于每个测试数据,第一行为一个整数 nn

第二行包含 nn 个整数 cic_i,表示第 ii 个气球最初的颜色。

Output

一行一个整数表示答案。

Samples

2
8
4 3 1 2 1 1 3 3
5
1 2 3 2 1
3
2

Limitation

对于 20%20\% 的数据,1cin101\le c_i\le n\le 10

对于 60%60\% 的数据,1cin1001\le c_i\le n\le 100

对于 100%100\% 的数据,1cin3×103,1t51\le c_i\le n\le 3\times10^3,1\le t\le 5

保证每种颜色最初出现不超过 1515 次。

[CZR-015] CZOJ Weekly Exercise Round 15——Where is R14?

未参加
状态
已结束
规则
IOI
题目
6
开始于
2024-8-25 17:00
结束于
2024-8-25 22:00
持续时间
5 小时
主持人
参赛人数
26