Одавно се зна за мистична својства низова којима је и битовска конјункција свих елемената већа од нуле и битовска ексклузивна дисјункција већа од нуле. Чаробњак Визаард је добио један овакав низ са \(N​\) елемената. Да би он добио мистична својства, Визаард на сваком од његових елемената може да примени једну од следеће две операције:

• Уколико је \(A_{i} > 0​\), може да смањи вредност елемeнту са индексом \(i​\). Овом операцијом вредност \(i​\)-тог елемента се претвара у \(A_{i}-1​\).
• Може да повећа вредност елементу са индексом \(i\). Овом операцијом вредност \(i\)-тог елeмента се претвара у \(A_{i}+1\).

Визаарда интересује колико најмање операција мора да примени тако да низ добије мистична својства, тј. да му битовска конјункција свих елемената буде већа од нуле и да му битовска ексклузивна дисјункција свих елемената буде већа од нуле.

Опис улаза

У првој линији налази се један број \(N\), дужина низа. У наредној линији налази се низ од \(N\) елемената.

Опис излаза

Исписати најмањи број операција потребних да и битовска конјункција и битовска ексклузивна дисјункција свих елемената буде већа од \(0\).

Пример

Улаз

4
5 2 3 3

Излаз

1

Објашњење примера

Приметимо да је \(5 \ \text{and} \ 2 \ \text{and} \ 3 \ \text{and} \ 3 = 0​\). Међутим приметимо да уколико други елемент смањимо за један, добијамо низ \([5,1, 3, 3]​\), за који важи \(5 \ \text{and} \ 1 \ \text{and} \ 3 \ \text{and} \ 3 = 1​\) и \(5 \ \text{xor} \ 1 \ \text{xor} \ 3 \ \text{xor} \ 3 = 4​\).

Ограничења

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

Постоје четири подзадатка:

• Подзадатак 1 [14 поена]: \(N, A_{i} \leq 16\).
• Подзадатак 2 [20 поена]: \(N \leq 10^3​\), \(A_{i} \leq 10^9​\).
• Подзадатак 3 [29 поена]: \(N \leq 3\cdot 10^4\), \(A_{i} \leq 10^9\).
• Подзадатак 4 [37 поена]: Нема додатних ограничења.

Напомена

Оператор конјункције у Pascal-u је означен са and, док у C++ га записујемо помоћу симбола &. Ова операција \(x\ \text{and} \ y\) се за ненегативне целе бројеве \(x,y\) дефинише на следећи начин. Прво се бројеви запишу у бинарном запису. Уколико један број има мање цифара од другог, дописују му се водеће нуле све док не буду имали исти број бинарних цифара. Тако се добијају два низа бинарних цифара, означимо их са \(a_1, \ldots, a_k\) и \(b_1, \ldots b_k\). Затим се за сваку позицију \(i \in \{1, \ldots, k \}\) рачуна \(c_i\) помоћу следећих правила:

• За \(a_{i} = 0, b_{i} = 0\) важи \(c_{i} = 0\)
• За \(a_{i} = 0, b_{i} = 1\) важи \(c_{i} = 0\)
• За \(a_{i} = 1, b_{i} = 0\) важи \(c_{i} = 0\)
• За \(a_{i} = 1, b_{i} = 1\) важи \(c_{i} = 1\)

Низ бинарних цифара \(c_1, \ldots, c_k\) (који можда има водеће нуле) је бинарни запис резултата, односно броја \(x \ \text{and} \ y\).

Битовска конјункција између \(n\) елемената \(x_{1},x_{2},...,x_{n}\) дефинише се као \(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}\).

Оператор ексклузивне дисјункције у Pascal-u је означен са xor, док у C++ га записујемо помоћу симбола ^. Ова операција \(x\ \text{xor} \ y​\) се за ненегативне целе бројеве \(x,y​\) дефинише на следећи начин. Прво се бројеви запишу у бинарном запису. Уколико један број има мање цифара од другог, дописују му се водеће нуле све док не буду имали исти број бинарних цифара. Тако се добијају два низа бинарних цифара, означимо их са \(a_1, \ldots, a_k​\) и \(b_1, \ldots b_k​\). Затим се за сваку позицију \(i \in \{1, \ldots, k \}​\) рачуна \(c_i​\) помоћу следећих правила:

• За \(a_{i} = 0, b_{i} = 0\) важи \(c_{i} = 0\)
• За \(a_{i} = 0, b_{i} = 1\) важи \(c_{i} = 1\)
• За \(a_{i} = 1, b_{i} = 0\) важи \(c_{i} = 1\)
• За \(a_{i} = 1, b_{i} = 1\) важи \(c_{i} = 0\)

Низ бинарних цифара \(c_1, \ldots, c_k\) (који можда има водеће нуле) је бинарни запис резултата, односно броја \(x \ \text{xor} \ y\).

Битовска ексклузивна дисјункција између \(n\) елемената \(x_{1},x_{2},...,x_{n}\) дефинише се као \(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}\).