Jocul DJ (“Dublu sau Jumate”) este noua provocare pentru concurenții de la ONI 2026.

La începutul jocului primiți un șir de numere naturale.

Scopul jocului este de a egaliza valorile din șir, adică de a transforma șirul dat într-un șir cu toate elementele egale. Pentru aceasta, aveți la dispoziție două tipuri de operații:

1. se selectează un element 𝑥 din șir și se înlocuiește cu 𝑥 · 2 + 1;
2. se selectează un element 𝑥 din șir și se înlocuiește cu câtul împărțirii întregi dintre 𝑥 și 2.

Cerința

Dat fiind un șir de numere naturale, scrieți un program care determină numărul total minim de operații necesare pentru egalizarea valorilor din șir.

Date de intrare

Fișierul de intrare dj.in conține pe prima linie numărul natural 𝑁 reprezentând numărul de elemente din șir. Pe a doua linie se află 𝑁 numere naturale separate prin câte un spațiu, reprezentând elementele șirului.

Date de ieșire

Fișierul de ieșire dj.out va conține o singură linie pe care se află numărul total minim de operații necesare pentru egalizarea valorilor din șirul dat.

Restricții și precizări

• 1 ≤ n ≤ 50 000
• 0 ≤ valorile din șir ≤ 2·105

Subtaskuri

• 2 ≤ 𝑁 ≤ 10, 0 ≤ valoarea maximă din șir ≤ 20;
• Pentru orice element din șir se aplică cel mult o operație;
• 2 ≤ 𝑁 ≤ 500, 21 ≤ valoarea maximă din șir ≤ 255;
• Fără restricții suplimentare.

Exemplul 1

dj.in

4
6 7 12 15

dj.out

6

Explicație

Numărul total minim de operații necesare pentru a egaliza valorile din șir este 6.

\( 6 \xrightarrow{2} 3\)
\( 7 \xrightarrow{2} 3\)
\( 12 \xrightarrow{2} 6 \xrightarrow{2} 3\)
\( 15 \xrightarrow{2} 7 \xrightarrow{2} 3\)

Exemplul 2

dj.in

4
2 7 3 12

dj.out

5

Explicație

Numărul total minim de operații necesare pentru a egaliza valorile din șir este 5.

\( 2 \xrightarrow{2} 1 \xrightarrow{1} 3\)
\( 7 \xrightarrow{2} 3\)
\( 12 \xrightarrow{2} 6 \xrightarrow{2} 3\)