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

Перегляд у форматі PDF

Надіслати розв'язок

Бали: 20
Time limit: 1.0s
Memory limit: 250M

Author:
Problem type

В Антона був масив \(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].


Коментарі

Ще немає коментарів.