CF2159D1.Inverse Minimum Partition (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, you are only asked to find $f(a)$. You can hack only if you solved all versions of this problem.

For some sequence $b$ of $k$ positive integers, the cost of the sequence is defined as follows$^{\text{∗}}$:

$$\\mathtt{cost}(b)=\\left\\lceil{\\frac{b\_k}{\\min(b\_1,b\_2,\\ldots,b\_k)}}\\right\\rceil$$

Assume that you partition a sequence $c$ into one or more sequences, so that the sequences become $c$ when concatenated. For example, when the sequence $c$ is $[3,1,4,1,5]$, a few valid ways to partition the sequence are $[[3,1],[4,1,5]]$, $[[3],[1,4,1],[5]]$, $[[3,1,4,1,5]]$. On the other hand, $[[3,1],[1,5]]$ and $[[3,4,1],[1,5]]$ are not valid ways to partition the sequence.

For a partition of a sequence $c$ of positive integers, the total cost of the partition is defined as the sum of the costs of each sequence in the partition. Then, let us define $f(c)$ as the minimum total cost to partition the sequence $c$.

Given a sequence $a$ of $n$ positive integers, you must compute the value of $f(a)$.

$^{\text{∗}}$Given a real value $x$, $\left\lceil{x}\right\rceil$ is defined as the smallest integer no less than $x$. For example, the value of $\left\lceil{3.14}\right\rceil$ is $4$.

这是该问题的简单版本。两个版本的区别在于，在本版本中，你只需计算 $f(a)$。仅当你解决了该问题的所有版本时，才可进行 hack。

对于某个由 $k$ 个正整数组成的序列 $b$，其代价定义如下$^{\text{∗}}$：

$$\mathtt{cost}(b)=\left\lceil{\frac{b_k}{\min(b_1,b_2,\ldots,b_k)}}\right\rceil$$

假设你将一个序列 $c$ 划分为一个或多个子序列，使得将这些子序列按顺序拼接后恰好得到 $c$。例如，当序列 $c$ 为 $[3,1,4,1,5]$ 时，一些合法的划分方式包括 $[[3,1],[4,1,5]]$、$[[3],[1,4,1],[5]]$、$[[3,1,4,1,5]]$；而 $[[3,1],[1,5]]$ 和 $[[3,4,1],[1,5]]$ 则不是合法的划分方式。

对于一个由正整数组成的序列 $c$ 的某种划分，该划分的总代价定义为划分所得各子序列代价之和。接着，我们定义 $f(c)$ 为划分序列 $c$ 所能得到的最小总代价。

给定一个长度为 $n$ 的正整数序列 $a$，你需要计算 $f(a)$ 的值。

$^{\text{∗}}$ 对于任意实数 $x$，$\left\lceil{x}\right\rceil$ 表示不小于 $x$ 的最小整数。例如，$\left\lceil{3.14}\right\rceil = 4$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 4\cdot 10^5$).

The second line of each test case contains $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^{18}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $4\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 4\cdot 10^5$）。

每个测试用例的第二行包含 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^{18}$）。

保证所有测试用例的 $n$ 之和不超过 $4\cdot 10^5$。

For each test case, output the answer to the problem on a separate line.

对于每个测试用例，在单独的一行上输出该问题的答案。

For the first test case, the partition $[[3,1,4,1],[5]]$ gives a total cost of $1+1=2$.

For the second test case, the partition $[[9,2,6,5,3],[5,8,9,7,9]]$ gives a total cost of $2+2=4$.

For the third test case, the partition $[[1],[2,3,4],[5,6,7,8]]$ gives a total cost of $1+2+2=5$.

For the fourth test case, the partition $[[1],[1\,000\,000\,000\,000\,000\,000]]$ gives a total cost of $1+1=2$.

对于第一个测试用例，划分 $[[3,1,4,1],[5]]$ 的总代价为 $1+1=2$。

对于第二个测试用例，划分 $[[9,2,6,5,3],[5,8,9,7,9]]$ 的总代价为 $2+2=4$。

对于第三个测试用例，划分 $[[1],[2,3,4],[5,6,7,8]]$ 的总代价为 $1+2+2=5$。

对于第四个测试用例，划分 $[[1],[1\,000\,000\,000\,000\,000\,000]]$ 的总代价为 $1+1=2$。