Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

#21613. 【PR #1】删数

Statistiques

给定一个长为 $n$ 的正整数序列 $a_1,\cdots,a_n$。

你可以进行若干次操作,每次操作你可以选择一个位置 $i\in[2,n-1]$ 使得 $a_i=\dfrac{a_{i-1}+a_{i+1}}{2}$,随后将 $a_i$ 删去,之后的数按顺序向前补空位。

求若干次操作后序列长度最小可以是多少。

输入格式

第一行,一个正整数 $T$,表示数据组数。之后对于每组数据:

  • 第一行,一个正整数 $n$;
  • 第二行,$n$ 个正整数 $a_1,\cdots,a_n$。

输出格式

对于每组数据,输出一行,一个正整数,表示答案。

样例一

input

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

output

2
4
2

explanation

对于第一组数据 $[1,2,3,4,5]$,依次删除 $2,4,3$ 即可。

对于第二组数据 $[1,3,5,6,7,8,10]$,依次删除 $3,7,8$ 即可。

对于第三组数据 $[1,1,1]$,删除中间的 $1$ 即可。

样例二

见下发文件,该样例符合测试点 $17\sim 20$ 的限制。

数据范围

本题共 $20$ 组测试点,各 $5$ 分。

对于所有数据,$n\ge 3$,$1 \le T\le 10^3$,$\sum n\le 3\cdot 10^5$,$1 \le a_i\le 10^9$ 。

测试点编号 $n\le$ $\sum n\le$ 特殊性质
$1\sim 3$ $15$ $400$ $ $
$4\sim 6$ $a_i=i$
$7\sim 8$ $a_i\le 3$
$9\sim 12$ $300$ $10^3$
$13\sim 16$ $3\cdot 10^3$ $10^4$
$17\sim 20$ $ $ $ $

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$