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

2020-2022 2023 Regulations Schedule RODO info Ranking

Problem description


Warszawskie wieżowce
(wiezowce-warszawskie)
Limit pamięci: 64 MB
Limit czasu: 1.00 s

Po długich tułaczkach Karol w końcu wylądował w Warszawie, teraz zostało jeszcze tylko wsiąść do samochodu i za dwie godzinki dojechać do domu.

Karol wsiadał już do samochodu, gdy ostatni raz spojrzał na panoramę N warszawskich wieżowców i tak się złożyło, że wszystkie z nich widoczne były jeden przy drugim w rzędzie. Przyjrzał się im uważnie i zauważył, że każdy z nich ma parzystą liczbę pięter, a ponadto nie ma dwóch budynków o jednakowej liczbie pięter. Podróżnik zaczął się zastanawiać nad tym ile inwersji, czyli takich par budynków, że wyższy stoi na lewo od niższego, jest obecnych w panoramie warszawskich wieżowców. Policzył to szybko, wsiadł do samochodu i odjechał.

W drodze jednak coś nie dawało mu spokoju, zastanawiał się nad tym, ile najwięcej inwersji mogłoby być obecnych w warszawskiej panoramie, gdyby któremuś z budynków dobudować lub zburzyć nieparzyście wiele pięter.

Niestety ta zagadka przerosła Karola i to Twoim zadaniem będzie napisanie programu, który wczyta wysokości kolejnych budynków warszawskiej panoramy i wyznaczy maksymalną liczbę inwersji, jaką można uzyskać po dobudowaniu lub zburzeniu nieparzystej liczby pięter jednego, dowolnego budynku.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, oznaczająca liczbę budynków obecnych w warszawskiej panoramie. W drugim wierszu wejścia znajduje się ciąg N liczb Ai, pooddzielanych pojedynczymi odstępami i oznaczający wysokości kolejnych budynków w panoramie od lewej do prawej.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba naturalna – maksymalna liczba inwersji, jaką można uzyskać po dobudowaniu lub zburzeniu nieparzyście wielu pięter dowolnego budynku.

Ograniczenia

1 ≤ N ≤ 100 000, 2 ≤ Ai ≤ 109.

Przykład

Wejście Wyjście Wyjaśnienie
8
30 16 4 2 10 12 14 8
21

Początkowo mamy 17 inwersji, a dobudowując do trzeciego wieżowca 11 pięter, otrzymamy 4 dodatkowe inwersje.