In one move, Milica can replace the whole string with $$$\texttt{AA} \ldots \texttt{A}$$$. In her second move, she can replace a prefix of length $$$k$$$ with $$$\texttt{BB} \ldots \texttt{B}$$$. The process takes no more than $$$2$$$ operations. The question remains — when can we do better?

In the hint section, we showed that the minimum number of operations is $$$0$$$, $$$1$$$, or $$$2$$$. We have $$$3$$$ cases:

1. No operations are needed if $$$s$$$ already contains $$$k$$$ characters $$$\texttt{B}$$$.

2. Else, we can use brute force to check if changing some prefix leads to $$$s$$$ having $$$k$$$ $$$\texttt{B}$$$s. If we find such a prefix, we print it as the answer, and use only one operation. There are $$$O(n)$$$ possibilities. implementing them takes $$$O(n)$$$ or $$$O(n^2)$$$ time.

3. Else, we use the two operations described in the hint section.

A fun fact is that only one operation is enough. Can you prove it?

If at some point Milena divides $$$a_i$$$ on $$$x$$$ and $$$y$$$, that will not affect the subarray right from $$$a_i$$$ (by dividing some element, it can only get smaller). That means we can try greedy from right to left.

After each operation number of elements increases by 1, so we need $$$m-1$$$ operations to divide some element on $$$m$$$ integers.

As we described in the hints, we will solve the array greedily from right to left. Let's assume we have sorted subarray $$$[a_{i+1}, \dots, a_n]$$$, and now we are operating on element $$$a_i$$$. Let $$$a_i$$$ be divided into integers $$$x_1,\dots,x_{m+1}$$$ after $$$m$$$ operations. As we want to make all $$$x_i$$$ as large as possible, to spend as few operations as possible on the left subarray, all $$$x_i$$$ will have the value $$$\lfloor \frac{a_i}{m+1} \rfloor$$$ or $$$\lceil \frac{a_i}{m+1} \rceil$$$. So in order to sort the array, $$$\lfloor \frac{a_i}{m+1} \rfloor \leq a_{i+1}$$$ must hold. Therefore, the minimum value of $$$m$$$ for which it is possible to sort the right subarray is $$$\lfloor \frac{a_i}{a_{i+1}} \rfloor-1$$$ or $$$\lfloor \frac{a_i}{a_{i+1}} \rfloor$$$. Do not forget to update the value of $$$a_i$$$ after the transition from $$$a_i$$$ to $$$a_{i-1}$$$.

...