题目描述
给定一个长度为$n$的正整数序列$a_1, ... , a_n$.
你可以进行若干次操作, 每次操作你可以选择一个位置$i \in [2, n - 1]$, 满足$a_i = \frac{a_{i-1} + a_{i+1}}{2}$, 然后将$a_i$删去, 之后的数按顺序向前补空位.
接下来的操作将在新序列上进行.
求若干次操作后, 最终序列的长度最小的是多少.
输入格式
第一行一个正整数$T$, 表示数据组数.
对于每组数据
第一行输入一个正整数$n$, 表示序列的长度.
接下来一行输入$n$个正整数, 分别表示$a_1, ... , a_n$.
输出格式
对于每组数据, 输出一行一个正整数, 表示答案.
数据范围
对于所有数据, 满足$1 \leq T \leq 10^3$, $3 \leq n$, $\sum{n} \leq 3 \cdot 10^5$, $1 \leq a_i \leq 10^9$.
样例输入
3
5
1 2 3 4 5
7
1 3 5 6 7 8 10
3
1 1 1
样例输出
2
4
2
题目来源
题目与数据均来自 Public Round #1 http://pjudge.ac/contest/883.
原题为International Zhautykov Olympiad 2022, Computer Science, Day 1, Problem 1.