Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024

2020-2022 2023 Regulations Schedule RODO info

Problem description


Zbiórka
(zbiorka)
Limit pamięci: 256 MB
Limit czasu: 2.00 s

Podczas porannej zbiórki kierowcy czołgów typu 1 i 2 ustawiają się w linii. W przypadku, gdy dwaj kierowcy tego samego typu czołgów stoją obok siebie, zaczynają rozmawiać, jak to ich typ czołgu jest lepszy od tego drugiego. Bardzo przeszkadza to generałowi podczas odliczania, więc zastanawia się, ilu minimalnie kierowców musi wyprosić, żeby mógł przeprowadzić zbiórkę w spokoju. Znając ustawienie kierowców w linii, pomóż mu, odpowiadając na to pytanie.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita N określająca liczbę kierowców. W drugim wierszu wejścia znajduje się N liczb każda wynosząca 1 lub 2, określająca, który typ czołgu prowadzi kierowca i.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć minimalna liczba kierowców, których trzeba wyprosić.

Ograniczenia

1 ≤ N ≤ 1 000 000.

Przykład

Wejście Wyjście Wyjaśnienie
6
1 1 2 2 2 1
3

Wystarczy wyprosić kierowców 2, 4 i 5, żeby nikt ze sobą nie rozmawiał.