A. Дуфф ба хүндийн өргөлт

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дуфф саяхнаас хүндийн өргөлтөөр хичээллэж байгаа. Малек түүнд ажил өгсөн. Тэр Дуффд хүндийг илэрхийлэх тоонуудын дараалал өгсөн. Дарааллын $i$-р элементийн хүнд нь $2^{w_{i}}$ паунд байна. Дуфф алхам бүртээ үлдсэн дарааллаас заримыг нь сонгон авч өргөж чадах ба өргөснийгөө дарааллаас хасна. Энэ үйлдлийг дараалал дуустал хийнэ. Малек түүнээс алхмын тоог хамгийн бага байлгахыг хүссэн.

Дуфф бол програмчлалын шүтэн бишрэгч. Энэ нь тэр алхам бүртээ хэрвээ $2^{a_{1}} + 2^{a_{2}} + ... + 2^{a_{k}} = 2^{x}$ буюу хэрвээ эдгээр тоонуудын нийлбэр 2-ийн $x$(эерэг бүхэл тоо) зэргээр илэрхийлэгдэж чадаж байвал $2^{a_{1}}, ..., 2^{a_{k}}$ энэ дарааллыг нэг алхамдаа өргөөд дарааллаас хасч чадах шалтгаан юм.

Дуфф бол програмчлалын шүтэн бишрэгч боловч програмчлагч биш учир таны тусламжийг хүсч байна. Түүнд хамгийн бага алхмын тоог олоход туслана уу.

Оролт

Оролтын эхний мөрөнд $n$ ($1 ≤ n ≤ 10^{6}$) бүхэл тоон утга байх ба хүндийг илэрхийлэх тоонуудын тоо юм.

Хоёр дахь мөрөнд зайгаар тусгаарласан $n$ ширхэг бүхэл тоон утга $w_{1}, ..., w_{n}$ байх ба ($0 ≤ w_{i} ≤ 10^{6}$ ба $1 ≤ i ≤ n$) эдгээр нь хүндийг илтгэх тооны 2-ийн зэрэг юм.

Гаралт

Алхмын хамгийн бага тоог нэг мөрөнд хэвлэнэ үү.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5
1 1 2 3 3
Гаралт
2
Оролт
4
0 1 2 3
Гаралт
4

Тэмдэглэл

Эхний жишээний дээр: Тохиромжтой ганц зам нь эхний алхам дээр эхний гурвыг өргөж хаяж чадах ба үлдсэнийг нь хоёрдугаар алхамдаа өргөж дарааллыг хоослох юм. Мөн бүгдийг нь нэг алхамд өргөж чадахгүй учир нь дарааллын нийлбэр 2-ийн зэргээр илэрхийлэгдэхгүй.

Хоёрдугаар жишээний дээр: Тохиромжтой ганцхан зам байгаа нь алхам бүртээ нэгийг өргөж дарааллаас хасах юм. 4-өөс бага алхамд дарааллыг хоослох боломжгүй юм учир нь 2-ийн зэргээр илэрхийлэгдэж чадах нэгээс олон хүндийг илэрхийлэх тоонууд алга байна.

Сэтгэгдлүүдийг ачааллаж байна...