CF2253F.4-beauty

For a set of integers $S$, define its divisibility characteristic as the number of ordered pairs $(x, y)$ such that $x \ne y$, $x$ and $y$ belong to $S$, and $x$ is divisible by $y$.

For a set of integers $A$, define its $4$-beauty as follows:

• consider all sets of four distinct numbers that belong to $A$ and form an arithmetic progression;
• find the maximum divisibility characteristic among all such sets.

If there are no suitable sets of four numbers, then the $4$-beauty equals $0$.

Initially, the set ${1, 2, \ldots, n}$ is given. You may remove numbers from it. Removing the number $i$ costs $m_i$ coins.

Calculate the minimum number of coins you have to spend in order to decrease the $4$-beauty of the set.

对于整数集合 $S$，定义其整除特征值为满足以下条件的有序对 $(x, y)$ 的个数：$x \ne y$，且 $x, y \in S$，且 $x$ 被 $y$ 整除。

对于整数集合 $A$，定义其4-美值如下：

• 考虑所有由 $A$ 中四个互不相同的数组成的等差数列；
• 在所有这些四元组中，找出最大的整除特征值。

若不存在满足条件的四元组，则该集合的 4-美值定义为 $0$。

初始时给定集合 $\{1, 2, \ldots, n\}$。你可以从中删除若干数字。删除数字 $i$ 的代价为 $m_i$ 枚金币。

请计算为使该集合的 4-美值降低所需花费的最少金币数。

The first line contains one integer $n$ ($4 \le n \le 5 \cdot 10^5$) — the number of elements in the initial set.

The second line contains $n$ integers $m_1, m_2, \ldots, m_n$ ($1 \le m_i \le 10^9$), where $m_i$ is the cost of removing the number $i$.

第一行包含一个整数 $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$ 的代价。

Print one integer — the minimum number of coins you have to spend in order to decrease the $4$-beauty of the set. It can be shown that it is always possible.

输出一个整数——为使该集合的 $4$-beauty 减小所需花费的最少硬币数。可以证明，这总是可行的。

In the first example, the only arithmetic progression of four numbers is $1, 2, 3, 4$. Its divisibility characteristic equals $4$. It is sufficient to remove the number $4$, paying $2$ coins.

In the second example, it is sufficient to remove the number $1$.

In the third example, it is optimal to remove the numbers $1$ and $6$, paying $2+3=5$ coins.

在第一个例子中，唯一的四项等差数列是 $1, 2, 3, 4$。其整除特征值为 $4$。只需移除数字 $4$，花费 $2$ 枚硬币。

在第二个例子中，只需移除数字 $1$。

在第三个例子中，最优策略是移除数字 $1$ 和 $6$，花费 $2+3=5$ 枚硬币。