#P15674. [Bulgarian2024训练营]Photography摄影

[Bulgarian2024训练营]Photography摄影

题目描述

Sashka 正在给保加利亚国家队拍合影。当前照片中有 NN 个人,从左到右第 ii 个人的身高为 aia_i。

若一个人位于中间位置 ii,即 1<i<N1<i<N,并且满足

ai=ai−1+ai+12,a_i=\frac{a_{i-1}+a_{i+1}}2,

则称这个人是一个“药瓶”。Sashka 可以让任意一个当前是“药瓶”的人离开照片。若第 ii 个人离开,左右两边的人会靠拢,身高序列变为

a1,a2,…,ai−1,ai+1,…,aN.a_1,a_2,\ldots,a_{i-1},a_{i+1},\ldots,a_N.

例如,若序列为 {1,3,6,9,4}\{1,3,6,9,4\},可以让身高为 66 的人离开,此后序列变为 {1,3,9,4}\{1,3,9,4\}。

Sashka 希望尽可能多的人离开照片。对于每个给定的身高序列,求最终照片中最少可以剩下多少人。

输入格式

第一行一个整数 TT,表示测试组数。

接下来每组数据包含两行:

第一行一个整数 NN。
第二行 NN 个整数 a1,a2,…,aNa_1,a_2,\ldots,a_N。

输出格式

对于每组数据,输出一行一个整数,表示最终最少剩下的人数。

数据范围

  • 1≤T≤10001\le T\le 1000;
  • 3≤N3\le N;
  • 所有测试组的 ∑N≤300000\sum N\le 300000;
  • 1≤ai≤1091\le a_i\le 10^9。

子任务

子任务 分值 NN ∑N\sum N 额外限制
1 0 - 样例
2 14 ≤15\le 15 ≤400\le 400 -
3 13 ≤300000\le 300000 ai=ia_i=i
4 9 ai≤3a_i\le 3
5 17 ≤300\le 300 ≤1000\le 1000 -
6 18 ≤3000\le 3000 ≤10000\le 10000
7 29 ≤300000\le 300000

只有通过某个子任务的所有测试点,才能获得该子任务分数。

样例

输入

3
5
1 2 3 4 5
7
1 3 5 6 7 8 10
3
1 1 1

输出

2
4
2