Кевин — студент из Вечно Спящего Города, который в настоящее время посещает математический класс, где учитель задает ему упражнения на деление.
На доске написаны две строки положительных целых чисел, каждая из которых содержит \( n \) чисел. Первая строка — это \( a_1, a_2, \ldots, a_n \), а вторая строка — \( b_1, b_2, \ldots, b_n \).
Для каждого упражнения на деление Кевин может выбрать любой отрезок \( [l, r] \) и найти минимальное значение \( x \) среди \( b_l, b_{l+1}, \ldots, b_r \). Затем он изменит каждое \( a_i \) для \( l \leq i \leq r \) на округление вверх от \( a_i \), деленного на \( x \).
Формально, он выбирает два целых числа \( 1 \leq l \leq r \leq n \), устанавливает \( x = \min_{l \leq i \leq r} b_i \), и изменяет все \( a_i \) для \( l \leq i \leq r \) на \( \lceil \frac{a_i}{x} \rceil \).
Кевин может покинуть класс и вернуться домой, когда все \( a_i \) станут равны \( 1 \). Он стремится уйти и хочет узнать минимальное количество упражнений на деление, необходимых для достижения этого.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество упражнений на деление, необходимых для выхода из класса.
Примечание
Для первого примера: \( [{\color{red}{5,4}},2]\xrightarrow[\min(b_1,b_2)=3]{\text{операция на отрезке }[1,2]}[{\color{red}{2,2,2}}]\xrightarrow[\min(b_1,b_2,b_3)=2]{\text{операция на отрезке }[1,3]}[1,1,1] \).
Для второго примера: \( [{\color{red}{3,6,1}},3,2]\xrightarrow[\min(b_1,b_2,b_3)=3]{\text{операция на отрезке }[1,3]}[1,{\color{red}{2,1,3}},2]\xrightarrow[\min(b_2,b_3,b_4)=2]{\text{операция на отрезке }[2,4]}[1,1,1,{\color{red}{2,2}}]\xrightarrow[\min(b_4,b_5)=2]{\text{операция на отрезке }[4,5]}[1,1,1,1,1] \).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
2
3
3
|