Divisive Battle

First, do not solve this by move parity. That is bait. Bob wins as soon as the array becomes non-decreasing, even if Alice was the one who made it happen. Alice only wins if the game gets stuck while the array is still decreasing somewhere.

The real structure is about prime factors.

Prime-Power Base

Define the base of a number like this:

• $1$ has base $1$.
• If $x=p^k$ for a prime $p$ and $k\ge 1$, then $x$ has base $p$.
• If $x$ has at least two distinct prime factors, call it bad.

Examples:

• $8=2^3$ has base $2$.
• $81=3^4$ has base $3$.
• $6=2\cdot 3$ is bad.
• $12=2^2\cdot 3$ is bad.

Now the answer is surprisingly clean:

If the array is already non-decreasing, Bob wins immediately.

Otherwise, Bob wins iff every number has a base and the base sequence is non-decreasing.

So for a non-sorted array, this is Bob-winning:

$[1, 2^{13}, 677]$

because the bases are

$1,2,677.$

But this is Alice-winning:

$[9,8]$

because the bases are

$3,2,$

and $3>2$.

Why Prime Powers Are Safe For Bob

Suppose every number is a prime power and the bases are non-decreasing.

Splitting a prime power preserves its base:

$p^k = p^u \cdot p^{k-u}.$

Both new numbers are still powers of $p$. So no matter how Alice or Bob splits things, the base sequence stays non-decreasing.

The game is finite, because each move breaks one composite into smaller factors. Eventually, if the game somehow has not ended earlier, every number is either $1$ or prime. At that point, the actual array equals its base sequence, which is non-decreasing.

That means Alice can never force an unsorted terminal position. Bob wins sooner or later. Not flashy, but brutally effective.

Why A Bad Number Lets Alice Win

Now suppose the array is not initially non-decreasing, and some number $x$ has at least two distinct prime factors.

Let $p$ be the smallest prime factor of $x$.

Alice splits $x$ like this:

$x \to \frac{x}{p},\ p.$

This is legal. Since $x$ is not a pure power of $p$, the number $x/p$ still contains some prime factor greater than $p$. In particular,

$\frac{x}{p} > p.$

So Alice immediately creates a local decrease:

$\frac{x}{p},\ p.$

The right element $p$ is prime, so it can never be changed. Everything produced from $x/p$ will always remain before that $p$.

For the array to ever become non-decreasing, the whole block coming from $x/p$ would need to fit before $p$, meaning all its final pieces would have to be at most $p$. But that is impossible, because $x/p$ contains a prime factor greater than $p$.

So Bob can never make the array sorted. Eventually the game ends unsorted, and Alice wins. Clean kill.

Why A Decrease In Bases Lets Alice Win

Now suppose every number is a prime power, but the bases are not non-decreasing.

Then there are adjacent numbers with bases

$p>q.$

So locally we have something like

$p^a,\ q^b.$

If $q^b$ is already just $q$ (or it is $1$), then the bad boundary is already fatal: everything from the left block is at least $p$, and $p>q$.

If $b\ge 2$, Alice splits the right number as

$q^b \to q,\ q^{b-1}.$

Now the array contains

$p^a,\ q,\ q^{b-1},$

and since $p>q$, we have an unavoidable decrease before the prime $q$.

Bob cannot fix this. Splitting $p^a$ only creates more powers of $p$, all still greater than $q$. The prime $q$ sits there like a tiny wall Bob cannot move.

So again, sortedness is impossible forever, and Alice wins.

Algorithm

For each test case:

1. If $a$ is already non-decreasing, print Bob.
2. Otherwise, compute the base of every $a_i$:
   • $1\mapsto 1$,
   • prime power $p^k\mapsto p$,
   • anything with multiple distinct prime factors is bad.
3. If any number is bad, print Alice.
4. If the base sequence decreases anywhere, print Alice.
5. Otherwise print Bob.

We precompute smallest prime factors up to $10^6$, so checking whether a number is a prime power is fast.

Complexity

The sieve costs

$O(A\log\log A)$

for $A=10^6$.

Each test case is linear in $n$, so the total work is

$O\left(10^6\log\log 10^6 + \sum n\right).$

Memory is $O(10^6)$.