Problem 584: divixori

În timpul concursului limita de timp a fost majorată la 1.5s. Acum am schimbat-o înapoi la 1s pentru a încuraja găsirea unor soluții mai eficiente.

Enunț

Omul fantastic găsește o permutare $p_1, p_2, ..., p_n$ de grad n. Acesta poate să modifice orice element al permutării, dar cu un cost. Astfel acesta alege $p_i$ și $d$ , astfel încât $1 \leq i \leq n$ și $d$ divide $p_i$ , iar $p_i$ se va modifica în $d$ , cu costul $p_i \oplus d$ . Toată lumea știe că lui nu îi place dezordinea. Acesta vrea să găsească costul minim pentru a obține un șir sortat crescător, nu neapărat strict, după finalul tuturor modificărilor. Totuși nu este tipul care ar implementa Slope-Trick la Marytone și decide să vă ceară ajutorul.

Cerință

Fiind date $n$ si permutarea $p$ , ajutați-l pe Omul fantastic.

Date de intrare

Fișierul de intrare divixori.in conține pe prima linie un număr natural $n$ . Pe a doua linie se vor afla $n$ numere naturale, $p_1, p_2, ..., p_n$ , reprezentând elementele permutării $p$ .

Date de ieșire

Fișireul de ieșire divixori.out conține un număr natural reprezentând costul minim pentru a obține un șir sortat crescător, nu neapărat strict, după finalul tuturor modificărilor.

Restricții și precizări

$1 \leq n \leq 10^6$
$1 \leq p_i \leq n, 1 \leq i \leq n$
Definiția operației $\oplus$
Atenție! Cerința este să implementați funcția solve(). Codul pe care îl veți trimite nu va conține functia main() — aceasta va fi înlocuită de funcția solve(). Iată un exemplu de un program valid:

long long solve(int n, int p[]) {
	return 0;
}

Pentru teste în valoare de $10p$ avem $1 \leq n \leq 10$
Pentru teste în valoare de $20p$ avem $1 \leq n \leq 10^3$
Pentru teste în valoare de $30p$ avem $1 \leq n \leq 10^5$
Pentru teste în valoare de $20p$ avem $1 \leq n \leq 5 \times 10^5$
Pentru teste în valoare de $20p$ avem $1 \leq n \leq 10^6$

Exemplul 1

divixori.in

6
1 4 2 3 6 5

divixori.out

Exemplul 2