Короткая логика

1. $$$(a_1,\dots,a_k) \gt (a_1,\dots,a_{k+1})$$$ $$$\Leftrightarrow$$$ $$$(a_1,\dots,a_k)=d\ge2$$$ и $$$a_{k+1}\not\equiv0\pmod d$$$.
2. $$$f(a)=0$$$ $$$\Leftrightarrow$$$ $$$a_1=(a_1,a_2)=\cdots=(a_1,\dots,a_n)$$$ $$$\Leftrightarrow$$$ $$$a_1=(a_1,\dots,a_n)$$$.
3. Для множества $$$S$$$ и $$$d\ge2$$$ обозначим $$$\operatorname{cnt}_d(S)=\left|{\,x\in S \mid d\mid x\,}\right|$$$. Если $$$\mathrm{cnt}_d(S)=|S|$$$, то $$$d$$$ делит всё ⇒ с таким $$$d$$$ спада сделать нельзя. Любая перестановка удовлетворяет $$$f \le \max_{d\ge2,\ \mathrm{cnt}_d \lt |S|}\mathrm{cnt}_d$$$.
4. Достижимость очевидна (ставим подряд все кратные $$$d$$$, затем любой некратный) ⇒

Почему достаточно только простых степеней $$$p^{\alpha_p+1}$$$

Пусть $$$G=\gcd(S)=\prod_{p} p^{\alpha_p}$$$ (берём только простые $$$p$$$, реально встречающиеся в $$$G$$$; для остальных $$$\alpha_p=0$$$). Тогда: Любой «полезный» делитель $$$d$$$, который может обеспечить спад, не делит весь набор, значит хотя бы по одному простому $$$p\mid d$$$ его показатель $$$e_p$$$ строго больше общей степени в $$$G$$$: $$$e_p\ge \alpha_p+1$$$. Множество $$${x:\ d\mid x}$$$ содержится в $$${x:\ p^{e_p}\mid x}$$$ для любого такого $$$p$$$. Следовательно

То есть составные делители не улучшают максимум: достаточно смотреть на одну простую степень, поднятую ровно «на один этаж» относительно общей. * Обратная сторона (достижимость): берём $$$p$$$ с максимальной $$$\mathrm{cnt}_{p^{\alpha_p+1}}(S)=c$$$. По определению $$$\alpha_p=\min v_p(x)$$$, значит есть элемент со степенью ровно $$$\alpha_p$$$ ⇒ $$$c \lt |S|$$$. Ставим сначала все $$$c$$$ чисел, делящихся на $$$p^{\alpha_p+1}$$$, затем число с $$$v_p=\alpha_p$$$. На позиции $$$k=c$$$ показатель по $$$p$$$ у префиксного $$$\gcd$$$ падает ⇒ спад есть.

Итог (строгое равенство):

Замечание: если $$$\gcd(S)=1$$$, то $$$\alpha_p=0$$$ для всех $$$p$$$, и формула даёт $$$g(S)=\max_p \mathrm{cnt}_{p}(S)$$$ — максимум числа кратных одному простому.

Переформулировка

Для префикса $$$P_i=[a_1,\dots,a_i]$$$, положим $$$G_i=\gcd(P_i)=\prod_p p^{\alpha_p(i)}$$$. Тогда

— то есть «сколько чисел в префиксе имеют по простому $$$p$$$ степень хотя бы на 1 больше общей минимальной степени по этому $$$p$$$ в $G_i$».

Примеры

• $$$S={6,12,18}$$$. $$$\gcd=6=2^1\cdot 3^1$$$. $$$\mathrm{cnt}_{2^{2}}=1$$$ (только 12), $$$\mathrm{cnt}_{3^{2}}=1$$$ (только 18) ⇒ $$$g=1$$$. Перестановка: (12,6,18).

• $$$S={8,4,2}$$$. $$$\gcd=2$$$ ⇒ $$$\alpha_2=1$$$. $$$\mathrm{cnt}_{2^{2}}=2$$$ (8,4) ⇒ $$$g=2$$$. Перестановка: (8,4,2).

• $$$\gcd(S)=1$$$: например $$$S={2,3,6,5}$$$. Макс по простым: по 2 — трое (2,6), по 3 — двое (3,6), по 5 — один ⇒ $$$g=2$$$. Ставим (2,6,3,5).