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.