Problem description

Krasnoludek Czyścioch nie cierpi bałaganu. Wszystko w jego domu musi mieć swoje miejsce, na półkach panuje ład i harmonia.

Ostatnio jego uwagę przykuł jeden regał, na którym trzyma książki o okładkach w kolorze czerwonym i niebieskim. Od ostatniego generalnego sprzątania domu jego kolekcja znacznie się zwiększyła, przez co w oczach Czyściocha kolejność książek na półce wygląda bardzo nieelegancko. Postanowił więc zająć się wreszcie tym tematem.

Czyścioch chciałby ustawić książki w taki sposób, aby żadne dwie z niebieską okładką nie stały bezpośrednio obok siebie. Aby tego dokonać, może on wyciągnąć wybraną z półki książkę i wstawić ją w dowolne inne miejsce. Chciałby wykonać minimalną liczbę takich przestawień książek – Czyścioch wolałby pozostawić siły na sprzątanie reszty swojego domu.

Napisz program, który znając kolory okładek książek na półce, wypisze ile co najmniej przestawień należy wykonać, żeby uzyskać interesujące Czyściocha ustawienie. Jeżeli nie istnieje ciąg przestawień po którym powyższy warunek byłby spełniony, należy wypisać  − 1.

Wejście

W pierwszym wierszu wejścia znajduje się liczba N, oznaczająca liczbę książek na półce. W drugim wierszu wejścia znajduje się ciąg liczb całkowitych P₁, P₂, …, P_N, którego wyrazy oznaczają kolory kolejnych książek, gdzie 0 oznacza kolor czerwony, a 1 kolor niebieski.

Wyjście

W pierwszym wierszu wyjścia należy wypisać najmniejsza liczbę przestawień książek lub  − 1 jeżeli odpowiedź nie istnieje.

Ograniczenia

1 ≤ N ≤ 10⁶, 0 ≤ P_i ≤ 1.

Przykłady

5
1 0 1 0 1

0

8
1 0 1 1 1 0 0 0

2

3
1 1 1

-1