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.

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 $ .

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.

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.