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 $ .

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 $ .

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 $ .