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 split $$$a_i$$$ into $$$x$$$ and $$$y$$$, that will not affect the subarray right from $$$a_i$$$ (by splitting some element, it can only get smaller). That means we can try greedy from right to left.

As we described in the hints, we will sort 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 splited 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 $$$\lceil \frac{a_i}{a_{i+1}} \rceil-1$$$. Do not forget to update the value of $$$a_i$$$ to $$$\lfloor \frac{a_i}{m+1} \rfloor$$$ after the transition from $$$a_i$$$ to $$$a_{i-1}$$$.

There are $$$q \leq 2\cdot 10^5$$$ queries: given an index $$$i$$$ and an integer $$$x>1$$$, set $$$a_i := \lceil \frac{a_i}{x} \rceil$$$. For each query, modify the array and print the answer to the original problem. Please note that queries stack.

We consider the vertices modulo p. Since $$$p$$$ is prime, there is a primitive root $$$g$$$ modulo $$$p$$$. How do we rewrite the condition of $$$x$$$ and $$$x^2$$$ being connected in a simpler way?

Following the hint, we conclude for each $$$0<x<p$$$ there exists $$$y$$$ such that $$$g^y \equiv x \ (\mod p)$$$. We rewrite the condition as $$$g^y$$$ and $$$g^{2y}$$$ being connected. Or even simpler, as $$$y$$$ and $$$2y$$$ being connected $$$(\mod p-1)$$$.

We are left to find the number of components in the graph with $$$k=p-1$$$ vertices, numbered from $$$0$$$ to $$$k-1$$$, in which $$$i$$$ and $$$2i$$$ are connected $$$(\mod k)$$$ for every $$$0 \leq i < k$$$. We add $$$1$$$ to the answer (as we did not include the case $$$x=0$$$ in the original graph).

If $$$k$$$ is even, notice how we can ignore all odd nodes, as we can merge them with even ones. Instead of merging, we can divide $$$k$$$ by $$$2$$$. We repeat the process as long as $$$k$$$ is divisible by $$$2$$$. Assume $$$k$$$ is odd from now on.

Let's consider some $$$x$$$, and the graph walk

At some point we will arrive at a node we already visited. In fact, all such walks are cyclic and every component of the graph consists of a single cycle. We only have to find the smallest positive integer $t$ such that $$$x \cdot 2^t \equiv x (\mod k)$$$ for every $$$x$$$. It is known that such $$$t$$$ exists. An issue we encounter is that $$$t$$$ is not constant per choice of $$$x$$$. But, we will try to "group" together similar $$$x$$$s. We want $$$t$$$ to be constant in a particular group. The number of components in the group is $$$\frac{G}{t}$$$, where $$$G$$$ is the group's size. The total number of components is equal to the sum over all groups.

If we fix some positive integer $$$d$$$, the smallest integer $$$t$$$ with $$$2^t \equiv 1 (\mod d)$$$ is obviously fixed. Furthermore for each $$$0 \leq x < d$$$ with $$$gcd(x,d) = 1$$$, we know that $$$x \cdot 2^t \equiv x (\mod d)$$$ and $$$t$$$ keeps the property of being the smallest such integer. This motivates us to fix some divisor $$$d$$$ of $$$k$$$ and consider $$$x$$$ with $$$gcd(x,k) = \frac{n}{d}$$$. Such $$$x$$$s belong to the same group. Notice how the groups are disjoint, and we only need to find the discrete log for each one (that is, $$$t$$$). Baby-step giant-step is a known algorithm which computes it in $$$O(\sqrt{s})$$$ complexity, where $$$s$$$ is the group's size. The total complexity is $$$O(\sqrt{n})$$$ per test case.

Prove that the worst case time complexity is exactly $$$O(\sqrt{n})$$$. That is, prove $$$\sum_{d|n} \sqrt{d} < c\cdot \sqrt{n}$$$ for some real constant $$$c$$$. Also try to come up with a test which runs in $$$O(\sqrt{n})$$$ with the constant as high as possible.