Farmer John's Last Wish

Let the current multiset be a prefix $S$ of size $m$. We need $g(S)$: the latest possible position where the prefix gcd can strictly decrease after some reordering.

What does a drop mean?

Suppose an ordering has a drop at position $k$. Let

$d=\gcd(b_1,b_2,\ldots,b_k).$

Then the next gcd is

$\gcd(d,b_{k+1}).$

This is smaller than $d$ exactly when $b_{k+1}$ is not divisible by $d$. No magic, no weird ordering trick. Just divisibility doing its usual thing.

So we need to choose some first block of $k$ numbers whose gcd is $d$, while leaving outside at least one number not divisible by $d$.

The key divisor view

Fix some possible gcd value $d$.

Only numbers divisible by $d$ can be placed in the first block. To maximize $k$, we would like to take as many of them as possible.

Let:

• $\text{cnt}[d]$ = how many current numbers are divisible by $d$,
• $\text{mgcd}[d]$ = gcd of all current numbers divisible by $d$.

If $\text{mgcd}[d]=d$, then taking all numbers divisible by $d$ gives prefix gcd exactly $d$. Great: we can make a first block of size $\text{cnt}[d]$.

If $\text{mgcd}[d]>d$, then every current number divisible by $d$ is also divisible by that larger common gcd. Any subset is still stuck with a gcd divisible by that larger value, so gcd exactly $d$ is impossible. That $d$ is useless.

One more condition: we need a remaining number not divisible by $d$. That is exactly

$\text{cnt}[d] < m.$

Therefore:

$$g(S)=\max \{\text{cnt}[d] : \text{mgcd}[d]=d \text{ and } \text{cnt}[d]<m\}.$$

If no such $d$ exists, the answer is $0$.

That formula is the whole problem. The rest is just maintaining it without doing something tragically slow.

Online prefix update

Process the array left to right. When a new value $x$ is appended, only divisors of $x$ change:

• $\text{cnt}[d]$ increases by $1$,
• $\text{mgcd}[d]$ becomes $\gcd(\text{mgcd}[d],x)$.

All other divisors keep the same count and same gcd.

Since answers never decrease, keep a running ans and only check newly improved candidates.

There is one subtle case: a divisor that does not divide $x$ might become valid because the prefix length increased. Which one matters?

Let $G$ be the gcd of the previous prefix. If $x$ is not divisible by $G$, then we can put all previous $i-1$ elements first. Their gcd is $G$, and $x$ breaks it, so we immediately get candidate $i-1$.

For any smaller divisor of the previous global gcd, the gcd of all previous elements is still $G$, not that smaller divisor, so it does not satisfy $\text{mgcd}[d]=d$. So the previous global gcd is the only non-divisor-of-$x$ candidate we need. Nice little trap, but not that nasty once you stare at it.

Algorithm

Precompute all divisors up to $2\cdot 10^5$.

For each test case:

1. Maintain arrays cnt[d] and mgcd[d].
2. Maintain global_gcd of the processed prefix.
3. Maintain current answer ans.
4. For each new number $x$ at position $i$:
   • If this is not the first number and $x$ is not divisible by the previous global_gcd, update ans = max(ans, i-1).
   • Update global_gcd.
   • For every divisor $d$ of $x$:
     • update cnt[d],
     • update mgcd[d],
     • if mgcd[d] == d and cnt[d] < i, update ans with cnt[d].
   • Output ans.

The condition cnt[d] < i means not all current numbers are divisible by $d$, so there is some number available to break the prefix gcd.

Why this is correct

First, any valid drop at position $k$ has prefix gcd $d$. The first $k$ numbers are all divisible by $d$, and the next number is not divisible by $d$. Therefore $k\le \text{cnt}[d]$, $\text{cnt}[d]<m$, and gcd exactly $d$ must be achievable. That requires $\text{mgcd}[d]=d$. So every possible answer is covered by the formula.

Second, if some $d$ satisfies $\text{mgcd}[d]=d$ and $\text{cnt}[d]<m$, place all numbers divisible by $d$ first. Their gcd is exactly $d$. Then place any number not divisible by $d$ next. The gcd strictly decreases right there, giving position $\text{cnt}[d]$. So every value in the formula is actually achievable.

Third, during an append, only divisors of the appended value can have changed divisor statistics. Old valid candidates stay valid, so the running answer keeps them. The only old invalid candidate that can become valid without being updated is the old global gcd, and only when the old global gcd does not divide the new value. That gives candidate $i-1$. So the incremental update checks everything it needs and nothing dumb.

Complexity

Precomputing divisors costs $O(N\log N)$ for $N=2\cdot 10^5$.

Each array element processes all of its divisors, so the total work is

$O\left(\sum_i \tau(a_i)\right),$

which is easily fine here. Memory is $O(N)$.