Пограбування масиву#11359
В Антона був масив , і він його дуже любив. Він знає декілька фактів про цей масив:
Сума елементів даного масиву — парне число.
Для будь-якого (1 \leq i < |A|) виконується A_i \leq A_{i+1}, де — розмір масиву .
0 \leq A_i \leq 1.
A_i — ціле число.
Одного разу, повертаючись додому, Антон помітив злого Гранді поряд зі своїм масивом. Він міг вкрасти один елемент з масиву . Вам дано масив — масив, який був, коли Антон прийшов додому. Знайдіть кількість способів додати не більше одного елемента до масиву , щоб отримати масив, який задовольняє наведеним вище умовам.
Перший рядок містить одне ціле число (1 \leq n \leq 10^5) — кількість елементів масиву .
Другий рядок містить цілих чисел B_i (0 \leq B_i \leq 1).
Виведіть одне ціле число — відповідь на задачу.
Example 1
Example 2
Example 3
Example 4
Example 5
Пояснення до першого прикладу:
Якщо нічого не додавати, вийде A = [0], що задовольняє умовам.
Якщо додати на початок масиву, вийде A = [0, 0], що задовольняє умовам.
Якщо додати на початок масиву, вийде A = [1, 0], що не задовольняє умовам.
Якщо додати в кінець масиву, вийде A = [0, 0], що задовольняє умовам.
Якщо додати в кінець масиву, вийде A = [0, 1], що не задовольняє умовам.
Пояснення до п'ятого прикладу:
Умовам задовольняють наступні масиви: [0, 0, 0, 0, \underline{1}, 1, 1, 1], [0, 0, 0, 0, 1, \underline{1}, 1, 1], [0, 0, 0, 0, 1, 1, \underline{1}, 1], [0, 0, 0, 0, 1, 1, 1, \underline{1}].