[R45D]货架和沙威玛 - 代码源竞赛平台

时空限制

1.5S/512M

题目描述

我要当总理～
那就来一场货架比赛吧！
『货架』

你要和善于谋略的张军师在货架上对决，货架上按顺序排了 $n$ 个调料品，第 $i$ 种风味值为 $a_i$。

为了取得胜利，你要拿一些调味品。你可以进行若干次（可以不进行操作）如下操作：

• 首先，选择一个区间 $[l,r]$（$l<r$），满足 $a_{l+1}-a_l=a_{l+2}-a_{l+1}=\dots=a_r-a_{r-1}$，即该区间的风味值形成了一个长度至少为 $2$ 的等差数列。
• 然后，将该区间从序列中删除。形式化的，数列将变为 $(a_1,a_2,\dots,a_{l-1},a_{r+1},\dots,a_n)$。

你需要求出最后货架上最少有几瓶调味品，这对于你的胜利至关重要。

你和张军师要比赛 $T$ 次，所以本题有多组测试。

格式

输入格式

第一行包含一个整数 $T$，表示测试组数。

对于每个测试数据，第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1\dots a_n$。

输出格式

输出 $T$ 行，对于第 $i$ 行，输出第 $i$ 个测试数据中最后货架上最少有几瓶调味品。

样例

样例输入 #1

3
5
1 6 3 2 5
4
114514 1919810 998244353 1
7
7 1 2 4 1 10 8

样例输出 #1

1
0
0

样例解释 #1

对于第一组测试数据，你可以选择删除区间 $[1,2],[4,5]$，最终剩下一个调味品。可以证明没有更优的解法。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

记 $N$ 为一个测试点内所有 $n$ 的和。

子任务编号	分数	$N\le$
$1$	$50$	$200$
$2$	$50$	$5000$

对于 $100\%$ 的数据，$1 \le N \le 5000,1 \le a_i \le 10^{9}$。