Kevin and Math Class
Contest: Codeforces Global Round 28
Difficulty rating: 2500
Tags: brute force, data structures, divide and conquer, dp, implementation, math, trees

Kevin is a student from Eversleeping Town, currently attending a math class where the teacher is giving him division exercises.

On the board, there are two rows of positive integers written, each containing $$$ n $$$ numbers. The first row is $$$ a_1, a_2, \ldots, a_n $$$, and the second row is $$$ b_1, b_2, \ldots, b_n $$$.

For each division exercise, Kevin can choose any segment $$$ [l, r] $$$ and find the smallest value $$$ x $$$ among $$$ b_l, b_{l+1}, \ldots, b_r $$$. He will then modify each $$$ a_i $$$ for $$$ l \leq i \leq r $$$ to be the ceiling of $$$ a_i $$$ divided by $$$ x $$$.

Formally, he selects two integers $$$ 1 \leq l \leq r \leq n $$$, sets $$$ x = \min_{l \leq i \leq r} b_i $$$, and changes all $$$ a_i $$$ for $$$ l \leq i \leq r $$$ to $$$ \lceil \frac{a_i}{x} \rceil $$$.

Kevin can leave class and go home when all $$$ a_i $$$ become $$$ 1 $$$. He is eager to leave and wants to know the minimum number of division exercises required to achieve this.

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

The first line of each test case contains an integer $$$ n $$$ ($$$ 1 \le n \leq 2 \cdot 10^5 $$$) — the length of the sequence $$$ a $$$ and $$$ b $$$.

The second line of each test case contains $$$ n $$$ integers $$$ a_1, a_2, \ldots, a_n $$$ ($$$ 1 \le a_i \le 10^{18} $$$) — the first row of integers on the board.

The third line of each test case contains $$$ n $$$ integers $$$ b_1, b_2, \ldots, b_n $$$ ($$$ 2 \le b_i \le 10^{18} $$$) — the second row of integers on the board.

It is guaranteed that the sum of $$$ n $$$ over all test cases doesn't exceed $$$ 2 \cdot 10^5 $$$.

Output format:
For each test case, output one integer — the minimum number of division exercises required to leave class.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
For the first test case: $$$ [{\color{red}{5,4}},2]\xrightarrow[\min(b_1,b_2)=3]{\text{operate segment }[1,2]}[{\color{red}{2,2,2}}]\xrightarrow[\min(b_1,b_2,b_3)=2]{\text{operate segment }[1,3]}[1,1,1] $$$.

For the second test case: $$$ [{\color{red}{3,6,1}},3,2]\xrightarrow[\min(b_1,b_2,b_3)=3]{\text{operate segment }[1,3]}[1,{\color{red}{2,1,3}},2]\xrightarrow[\min(b_2,b_3,b_4)=2]{\text{operate segment }[2,4]}[1,1,1,{\color{red}{2,2}}]\xrightarrow[\min(b_4,b_5)=2]{\text{operate segment }[4,5]}[1,1,1,1,1] $$$.

Example input:
3
3
5 4 2
6 3 2
5
3 6 1 3 2
3 5 3 2 2
6
8 3 3 7 5 8
3 2 3 4 2 3

Example output:
2
3
3

Editorial:
Hint #1: Can you find a strategy such that only $$$n$$$ intervals might be operated on?
Hint #2: By operating on the entire sequence in each step, the answer can be made $$$\leq 63$$$.
Construct a min Cartesian tree for the sequence $$$b$$$. It is easy to observe that we will only operate on the intervals defined by this Cartesian tree.
• Proof: For any $$$b_x$$$, find the last $$$b_p \leq b_x$$$ on its left and the first $$$b_q < b_x$$$ on its right. If we want to divide the interval by $$$b_x$$$, the operation interval cannot include both $$$p$$$ and $$$q$$$. At the same time, choosing the largest possible interval is always optimal. Hence, the operation interval must be $$$[p+1, q-1]$$$. All such intervals are exactly the intervals corresponding to the Cartesian tree.
To solve the problem, we can use DP on the Cartesian tree. Let $$$f_{u,i}$$$ represent the minimum possible maximum value of $$$a_x$$$ within the subtree rooted at $$$u$$$ after performing $$$i$$$ operations on all positions within that subtree.
When merging, suppose the two child subtrees of $$$u$$$ are $$$ls$$$ and $$$rs$$$. The transition can be written as:
$$$$$$ f_{u,k}=\min_{i+j=k}\left(\max(f_{ls,i},f_{rs,j},a_u)\right) $$$$$$
Then consider division at the position corresponding to $$$b_u$$$, which updates the DP state:
$$$$$$ f_{u,k+1}\leftarrow\left\lceil\frac{f_{u,k}}{b_u}\right\rceil $$$$$$
Since operating on the entire sequence repeatedly can ensure that $$$\log_2(\max(a_i)) \leq 63$$$ operations suffice, the second dimension of the DP state only needs to be defined for $$$0 \sim 63$$$. Thus, the time complexity for this approach is $$$O(n \log^2 a)$$$.
The bottleneck of this approach lies in merging the DP states of the two subtrees. Observing that $$$f_{u,i}$$$ is monotonically non-increasing, the $$$\min-\max$$$ convolution for $$$f_{ls,i}$$$ and $$$f_{rs,i}$$$ is equivalent to merging two sequences using a merge sort-like approach. This reduces the merging complexity to $$$O(\log a)$$$.
Consequently, the overall complexity becomes $$$O(n \log a)$$$, which is an optimal solution.