CF2253F 4-beauty

对于一个整数集合 $S$，定义其可整除性特征为满足 $x \ne y$，$x$ 和 $y$ 都属于 $S$，且 $x$ 能被 $y$ 整除的有序对 $(x, y)$ 的数量。 给定一个整数集合 $A$，定义其 $4$-美丽度如下： - 考虑所有属于 $A$ 且能组成等差数列的四个不同数的集合； - 在所有这样的集合中，找到可整除性特征的最大值。 如果不存在满足条件的四元组，则 $4$-美丽度为 $0$。 最初给定集合 $\{1, 2, \ldots, n\}$。你可以从中移除若干数。移除数字 $i$ 需要花费 $m_i$ 个硬币。 请计算，为了减少该集合的 $4$-美丽度，最少需要花费多少个硬币。

第一行包含一个整数 $n$（$4 \le n \le 5 \cdot 10^5$），表示初始集合的元素个数。 第二行包含 $n$ 个整数 $m_1, m_2, \ldots, m_n$（$1 \le m_i \le 10^9$），其中 $m_i$ 表示移除数字 $i$ 的代价。

输出一个整数——为使集合的 $4$-美丽度下降，所需花费的最小硬币数。可以保证总是有办法实现。

在第一个样例中，唯一的四元等差数列是 $1, 2, 3, 4$，其可整除性特征等于 $4$。只需移除 $4$，花费 $2$ 个硬币即可。 在第二个样例中，只需移除 $1$ 即可。 在第三个样例中，最优操作是移除 $1$ 和 $6$，共花费 $2+3=5$ 个硬币。 由 ChatGPT 5 翻译