В Антона був масив A і він його дуже любив. Він знає декілька фактів про цей масив:
Сума елементів даного масиву — парне число
Для будь-якого i (1≤i<∣A∣) виконується Ai≤Ai+1, де ∣A∣ — розмір масиву A.
0≤Ai≤1.
Ai — ціле число.
Один раз, повертаючись додому, Антон помітив злого Гранді поряд зі своїм масивом. Він міг вкрасти один елемент з масиву A. Вам дано масив B — масив, який був, коли Антон прийшов додому. Знайдіть кількість способів додати не більше одного елементу до масиву B, щоб вийшов масив, який задовольняє умовам вище.
Перший рядок містить одне ціле число n (1≤n≤105) — кількість елементів масиву B.
Другий рядок містить n цілих чисел Bi (0≤Bi≤1).
Виведіть одне ціле число — відповідь на задачу.
Пояснення до першого прикладу:
Якщо нічого не додавати вийде 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].