Hints: Rational Bubble Sort

Replacing $(a_i, a_{i+1})$ by their average sets both to $\frac{a_i+a_{i+1}}{2}$. What happens to the sum of all elements in the array after one operation?

Answer to Hint 1: The sum is preserved: $a_i + a_{i+1}$ becomes $2 \cdot \frac{a_i+a_{i+1}}{2}$. Hence the multiset of values evolves, but the total sum $S = \sum a_j$ is an invariant (as a rational number).

What rational number is therefore fixed forever, no matter how you operate?

Answer to Hint 2: The average $\frac{S}{n}$ is invariant. For the final array to be sorted nondecreasing, a necessary condition is that this average equals the average of any sorted sequence with the same sum—so think about whether $\frac{2S}{n}$ must be an integer and how entries can converge toward that average.

Answer to Hint 3: If $2S$ is divisible by $n$, let $A = \frac{2S}{n}$ (twice the average, an integer in the reference solution’s scaling). You can try to pair adjacent elements that sum to $A$, or leave a position alone if already $a_i = A/2$.

Scan left to right: if $a_{\text{ptr}} = A/2$, advance; else if $a_{\text{ptr}} + a_{\text{ptr}+1} = A$, advance by $2$; else fail this branch.

Answer to Hint 4: If that greedy partition of the line into singletons-at-$A/2$ and adjacent pairs summing to $A$ covers the whole array, answer Yes: the operation can propagate averages so each block approaches the common mean.

If $2S \not\equiv 0 \pmod n$, this exact pairing cannot close—but another obstruction may still allow sorting.

Answer to Hint 5: If the divisibility check fails or the greedy pairing fails, the answer is still Yes if there exists an index $i$ ($1 \le i \lt n$) such that the strict inequality of left vs right average holds:

$$ \frac{a_1 + \cdots + a_i}{i} ;<; \frac{a_{i+1} + \cdots + a_n}{n-i}. $$

(Integers compared as cross-multiplying fractions: $\text{num}_L \cdot \text{den}_R < \text{num}_R \cdot \text{den}_L$.)

Geometrically, you can drive values so the left block stays below the right block while converging, then smooth toward sorted order. If no such split exists, answer No.

Answer to Hint 6: Implementation is $O(n)$ per test: first try the average-based pairing; on failure, scan $i$ for the strict average gap. This matches the reference decision tree.