Пограбування масиву

В Антона був масив $A$ і він його дуже любив. Він знає декілька фактів про цей масив:

• Сума елементів даного масиву — парне число

• Для будь-якого $i$ ($1\le i<|A|$) виконується $A_i\le A_{i+1}$, де $|A|$ — розмір масиву $A$.

• $0\le A_i\le 1$.

• $A_i$ — ціле число.

Один раз, повертаючись додому, Антон помітив злого Гранді поряд зі своїм масивом. Він міг вкрасти один елемент з масиву $A$. Вам дано масив $B$ — масив, який був, коли Антон прийшов додому. Знайдіть кількість способів додати не більше одного елементу до масиву $B$, щоб вийшов масив, який задовольняє умовам вище.

Input

Перший рядок містить одне ціле число $n$ ($1\le n\le 10^5$) — кількість елементів масиву $B$.

Другий рядок містить $n$ цілих чисел $B_i$ ($0\le B_i\le 1$).

Output

Виведіть одне ціле число — відповідь на задачу.

Examples

Note

Пояснення до першого прикладу:

Якщо нічого не додавати вийде $A=[0]$, що задовольняє умовам.

Якщо додати $0$ в початок масиву вийде $A=[$0, $0]$, що задовольняє умовам.

Якщо додати $1$ в початок масиву вийде $A=[$1, $0]$, що не задовольняє умовам.

Якщо додати $0$ в кінець масиву вийде $A=[0,$ 0$]$, що задовольняє умовам.

Якщо додати $1$ в кінець масиву вийде $A=[0,$ 1$]$, що не задовольняє умовам.

Пояснення до п'ятого прикладу:

Умови задовольняють наступні масиви $[0,0,0,0,$ 1$,1,1,1]$, $[0,0,0,0,1,$ 1$,1,1]$, $[0,0,0,0,1,1,$ 1$,1]$, $[0,0,0,0,1,1,1,$1$]$.