Odavno se zna za mistična svojstva nizova kojima je i bitovska konjunkcija svih elemenata veća od nule i bitovska ekskluzivna disjunkcija veća od nule. Čarobnjak Vizaard je dobio jedan ovakav niz sa \(N​\) elemenata. Da bi on dobio mistična svojstva, Vizaard na svakom od njegovih elemenata može da primeni jednu od sledeće dve operacije:

• Ukoliko je \(A_{i} > 0​\), može da smanji vrednost elementu sa indeksom \(i​\). Ovom operacijom vrednost \(i​\)-tog elementa se pretvara u \(A_{i}-1​\).
• Može da poveća vrednost elementu sa indeksom ~i~. Ovom operacijom vrednost ~i~-tog elementa se pretvara u ~A_{i}+1~.

Vizaarda interesuje koliko najmanje operacija mora da primeni tako da niz dobije mistična svojstva, tj. da mu bitovska konjunkcija svih elemenata bude veća od nule i da mu bitovska ekskluzivna disjunkcija svih elemenata bude veća od nule.

Opis ulaza

U prvoj liniji nalazi se jedan broj ~N~, dužina niza. U narednoj liniji nalazi se niz od ~N~ elemenata.

Opis izlaza

Ispisati najmanji broj operacija potrebnih da i bitovska konjunkcija i bitovska ekskluzivna disjunkcija svih elemenata bude veća od ~0~.

Primer

Ulaz

4
5 2 3 3

Izlaz

1

Objašnjenje primera

Primetimo da je \(5 \ \text{and} \ 2 \ \text{and} \ 3 \ \text{and} \ 3 = 0​\). Međutim primetimo da ukoliko drugi element smanjimo za jedan, dobijamo niz \([5,1, 3, 3]​\), za koji važi \(5 \ \text{and} \ 1 \ \text{and} \ 3 \ \text{and} \ 3 = 1​\) i \(5 \ \text{xor} \ 1 \ \text{xor} \ 3 \ \text{xor} \ 3 = 4​\).

Ograničenja

• ~2 \leq N \leq 5 \cdot 10^5~
• ~0 \leq A_{i} \leq 10^{18}~

Postoje četiri podzadatka:

• Podzadatak 1 [14 poena]: ~N, A_{i} \leq 16~.
• Podzadatak 2 [20 poena]: \(N \leq 10^3​\), \(A_{i} \leq 10^9​\).
• Podzadatak 3 [29 poena]: ~N \leq 3\cdot 10^4~, ~A_{i} \leq 10^9~.
• Podzadatak 4 [37 poena]: Nema dodatnih ograničenja.

Napomena

Operator konjunkcije u Pascal-u je označen sa and, dok u C++ ga zapisujemo pomoću simbola &. Ova operacija ~x\ \text{and} \ y~ se za nenegativne cele brojeve ~x,y~ definiše na sledeći način. Prvo se brojevi zapišu u binarnom zapisu. Ukoliko jedan broj ima manje cifara od drugog, dopisuju mu se vodeće nule sve dok ne budu imali isti broj binarnih cifara. Tako se dobijaju dva niza binarnih cifara, označimo ih sa ~a_1, \ldots, a_k~ i ~b_1, \ldots b_k~. Zatim se za svaku poziciju ~i \in \{1, \ldots, k \}~ računa ~c_i~ pomoću sledećih pravila:

• Za ~a_{i} = 0, b_{i} = 0~ važi ~c_{i} = 0~
• Za ~a_{i} = 0, b_{i} = 1~ važi ~c_{i} = 0~
• Za ~a_{i} = 1, b_{i} = 0~ važi ~c_{i} = 0~
• Za ~a_{i} = 1, b_{i} = 1~ važi ~c_{i} = 1~

Niz binarnih cifara ~c_1, \ldots, c_k~ (koji možda ima vodeće nule) je binarni zapis rezultata, odnosno broja ~x \ \text{and} \ y~.

Bitovska konjunkcija između ~n~ elemenata ~x_{1},x_{2},...,x_{n}~ definiše se kao ~x_{1} \ \text{and} \ x_{2} \ \text{and} \ ... \ \text{and} \ x_{n} = (...(((x_{1} \ \text{and} \ x_{2}) \ \text{and} \ x_{3}) \ \text{and} \ x_{4})...) \ \text{and} \ x_{n}~.

Operator ekskluzivne disjunkcije u Pascal-u je označen sa xor, dok u C++ ga zapisujemo pomoću simbola ^. Ova operacija \(x\ \text{xor} \ y​\) se za nenegativne cele brojeve \(x,y​\) definiše na sledeći način. Prvo se brojevi zapišu u binarnom zapisu. Ukoliko jedan broj ima manje cifara od drugog, dopisuju mu se vodeće nule sve dok ne budu imali isti broj binarnih cifara. Tako se dobijaju dva niza binarnih cifara, označimo ih sa \(a_1, \ldots, a_k​\) i \(b_1, \ldots b_k​\). Zatim se za svaku poziciju \(i \in \{1, \ldots, k \}​\) računa \(c_i​\) pomoću sledećih pravila:

• Za ~a_{i} = 0, b_{i} = 0~ važi ~c_{i} = 0~
• Za ~a_{i} = 0, b_{i} = 1~ važi ~c_{i} = 1~
• Za ~a_{i} = 1, b_{i} = 0~ važi ~c_{i} = 1~
• Za ~a_{i} = 1, b_{i} = 1~ važi ~c_{i} = 0~

Niz binarnih cifara ~c_1, \ldots, c_k~ (koji možda ima vodeće nule) je binarni zapis rezultata, odnosno broja ~x \ \text{xor} \ y~.

Bitovska ekskluzivna disjunkcija između ~n~ elemenata ~x_{1},x_{2},...,x_{n}~ definiše se kao ~x_{1} \ \text{xor} \ x_{2} \ \text{xor} \ ... \ \text{xor} \ x_{n} = (...(((x_{1} \ \text{xor} \ x_{2}) \ \text{xor} \ x_{3}) \ \text{xor} \ x_{4})...) \ \text{xor} \ x_{n}~.