Problems
Пограбування масиву
Пограбування масиву
В Антона був масив $A$ і він його дуже любив. Він знає декілька фактів про цей масив:
\begin{itemize}
\item Сума елементів даного масиву --- парне число
\item Для будь-якого $i$ ($1 \le i < |A|$) виконується $A_i \le A_{i+1}$, де $|A|$ --- розмір масиву $A$.
\item $0 \le A_i \le 1$.
\item $A_i$ --- ціле число.
\end{itemize}
Один раз, повертаючись додому, Антон помітив злого Гранді поряд зі своїм масивом. Він міг вкрасти один елемент з масиву $A$. Вам дано масив $B$ --- масив, який був, коли Антон прийшов додому. Знайдіть кількість способів додати не більше одного елементу до масиву $B$, щоб вийшов масив, який задовольняє умовам вище.
\InputFile
Перший рядок містить одне ціле число $n$ ($1 \le n \le 10^5$) --- кількість елементів масиву $B$.
Другий рядок містить $n$ цілих чисел $B_i$ ($0 \le B_i \le 1$).
\OutputFile
Виведіть одне ціле число --- відповідь на задачу.
\Note
Пояснення до першого прикладу:
Якщо нічого не додавати вийде $A = [0]$, що задовольняє умовам.
Якщо додати $0$ в початок масиву вийде $A = [$\textbf{\underline{0}}, $ 0]$, що задовольняє умовам.
Якщо додати $1$ в початок масиву вийде $A = [$\textbf{\underline{1}}, $0]$, що не задовольняє умовам.
Якщо додати $0$ в кінець масиву вийде $A = [0,$ \textbf{\underline{0}}$]$, що задовольняє умовам.
Якщо додати $1$ в кінець масиву вийде $A = [0,$ \textbf{\underline{1}}$]$, що не задовольняє умовам.
Пояснення до п'ятого прикладу:
Умови задовольняють наступні масиви $[0,0,0,0,$ \textbf{\underline{1}}$,1,1,1]$, $[0,0,0,0,1,$ \textbf{\underline{1}}$,1,1]$, $[0,0,0,0,1,1,$ \textbf{\underline{1}}$,1]$, $[0,0,0,0,1,1,1,$\textbf{\underline{1}}$]$.
Input example #1
1 0
Output example #1
3
Input example #2
1 1
Output example #2
2
Input example #3
2 1 0
Output example #3
0
Input example #4
5 0 0 0 1 1
Output example #4
5
Input example #5
7 0 0 0 0 1 1 1
Output example #5
4