AT_utpc2024_q.Quadratic Pieces

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$。

我们称，对于所有满足 $1 \le L \le R \le N$ 的整数 $L$、$R$，由它们确定的连续子序列 $(A_L, A_{L + 1}, \dots, A_R)$，如果满足下述条件，则称该连续子序列是二次函数的：

• 存在某些实数 $a, b, c$，使得对于所有满足 $L \le i \le R$ 的整数 $i$，都有 $A_i = a i^2 + b i + c$。

请你将整数序列 $A$ 分割成若干连续的、二次函数的子序列。输出所有可能的分割方案中，最少可以分成多少个这样的子序列。

有 $T$ 组测试数据，请分别输出每组的答案。

输入按以下格式从标准输入读入。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

每组测试数据格式如下：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出 $T$ 行。第 $i$ 行输出第 $i$ 组测试数据对应的答案。

样例解释 1

以第 $1$ 组测试数据为例，给定的序列可以划分为 $3$ 个连续的、二次函数的子序列 $(-16, -9, -4, -1),\, (0, 0, 0),\, (0, 1, 4, 9, 16)$。事实上，对于每个子序列，分别有 $(a, b, c) = (-1, 10, -25),\, (0, 0, 0),\, (1, -16, 64)$ 满足条件。无法将其划分为不超过 $2$ 个连续的、二次函数的子序列，所以答案是 $3$。

请注意，第 $4$ 组测试数据的输入可能超出 32 位整数的范围。

数据范围

• 所有输入均为整数。
• $1 \le T \le 10^5$
• $1 \le N \le 2 \times 10^5$
• $-10^{18} \le A_i \le 10^{18}$
• 对于单个输入内所有测试数据，$N$ 的总和不超过 $2 \times 10^5$。

由 ChatGPT 5 翻译