시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB61372560.976%

문제

Pliszka alternująca (Motacilla alterna) to gatunek ptaka z rodziny pliszkowatych. Wyróżnia go charakterystyczny śpiew, w którym wysokość tonu kolejnych dźwięków naprzemiennie rośnie i maleje. Dla przykładu, jeżeli będziemy reprezentować wysokości dźwięków za pomocą liczb całkowitych, to pliszka alternująca może zaśpiewać [2, 1, 3] i [4, 5, −6, −5], ale nie [1, 2, 3, 2] i [6, 5, 5, 4]. W celu nagrania tych fascynujących stworzeń ornitolog Bajtazar pozostawił swój dyktafon na kilka dni w lesie. Teraz zastanawia się, czy nagrane dźwięki są podobne do śpiewu pliszki.

Napisz program, który dla danego ciągu wysokości dźwięków wyznaczy minimalną liczbę jego wyrazów, które trzeba zmienić na dźwięk o dowolnej całkowitoliczbowej wysokości z przedziału [−109, 109], żeby ciąg przedstawiał możliwy śpiew pliszki alternującej.

입력

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita n (3 ≤ n ≤ 50 000), oznaczająca długość nagrania.

Kolejny wiersz zawiera n liczb całkowitych a1, a2, . . . , an (−1 000 000 ≤ ai ≤ 1 000 000), gdzie ai jest wysokością i-tego dźwięku w nagraniu.

출력

Na wyjściu powinna znaleźć się jedna liczba całkowita, oznaczająca minimalną liczbę zmienionych dźwięków.

예제 입력 1

5
4 1 3 3 1

예제 출력 1

1

예제 입력 2

4
-1000000 -1000000 -1000000 -1000000

예제 출력 2

2

힌트

Wyjaśnienie przykładów: W pierwszym teście przykładowym, aby ciąg mógł zostać zaśpiewany przez pliszkę alternującą, wystarczy zmienić czwarty wyraz ciągu, na przykład na −1. W drugim teście przykładowym trzeba zmienić co najmniej dwa wyrazy, otrzymując na przykład ciąg [−1 000 001, −1 000 000, −1 000 002, −1 000 000].