CF1995C Squaring

ikrpprpp found an array $ a $ consisting of integers. He likes justice, so he wants to make $ a $ fair — that is, make it non-decreasing. To do that, he can perform an act of justice on an index $ 1 \le i \le n $ of the array, which will replace $ a_i $ with $ a_i ^ 2 $ (the element at position $ i $ with its square). For example, if $ a = [2,4,3,3,5,3] $ and ikrpprpp chooses to perform an act of justice on $ i = 4 $ , $ a $ becomes $ [2,4,3,9,5,3] $ . What is the minimum number of acts of justice needed to make the array non-decreasing?

N/A

N/A

In the first test case, there's no need to perform acts of justice. The array is fair on its own! In the third test case, it can be proven that the array cannot become non-decreasing. In the fifth test case, ikrpprppp can perform an act of justice on index 3, then an act of justice on index 2, and finally yet another act of justice on index 3. After that, $ a $ will become $ [4, 9, 16] $ .