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

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

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

Знайдiть кiлькiсть способiв додати не бiльше одного елементу до масиву ~B~, щоб вийшов масив, який задовольняє умовам вище.

Формат вхiдних даних

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

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

Формат вихiдних даних

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

Приклад вхідних даних

1
0

Приклад вихідних даних

3

Приклад вхідних даних

1
1

Приклад вихідних даних

2

Приклад вхідних даних

2
1 0

Приклад вихідних даних

0

Приклад вхідних даних

5
0 0 0 1 1

Приклад вихідних даних

5

Приклад вхідних даних

7
0 0 0 0 1 1 1

Приклад вихідних даних

4

Зауваження

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

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

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

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

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

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

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

Умови задовольняють наступнi масиви [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].